32pts Dijkstra 求助
查看原帖
32pts Dijkstra 求助
1118893
Dark_Star楼主2024/7/3 16:09
#include<bits/stdc++.h>
//#define int long long
#define little_dog puts("OvO,2021zjhs005 is better than me.")
#define lcfollower break
#define _2021zjhs005 continue
#define inf 0x3f3f3f3f
#define infi 0x3f3f3f3f3f3f3f3fll
#define up(i,x,y) for(register int i=x;i<=y;++i)
#define dn(i,x,y) for(register int i=x;i>=y;--i)
using namespace std;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return x*f;}
inline void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10|48);}
inline void writeln(int x){write(x),putchar('\n');}
inline void writesp(int x){write(x),putchar(' ');}
inline char getchars(){char ch=getchar();while(ch!='\\'&&ch!='/')ch=getchar();return ch;}
struct lc{
	inline void fre(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
	inline void ext(){exit(0);}
};namespace LC{
	int head[1000001],tot=0,dis[1000001];bool vis[1000001];
	struct forward_star{int v,w,nxt;}a[4000001];
	void add(int u,int v,int w){
		a[++tot].v=v,a[tot].w=w;
		a[tot].nxt=head[u];
		head[u]=tot;
	}struct node{int dis,u;bool operator>(const node& a)const{return dis>a.dis;}};
	priority_queue<node,vector<node>,greater<node> >q;
	int dijkstra(int s,int t){
		memset(dis,0x3f,sizeof(dis));
		dis[s]=0,q.push({0,s});
		while(!q.empty()){
			int u=q.top().u;
			q.pop();
			if(vis[u])continue;
			vis[u]=1;
			for(register int i=head[u];i;i=a[i].nxt){
				int v=a[i].v,w=a[i].w;
				if(dis[v]>dis[u]+w){
					dis[v]=dis[u]+w;
					q.push({dis[v],v});
				}
			}
		}return dis[t];
	}inline signed main(){
		lc follower;
//		follower.fre();
		int n=read(),m=read();
		up(i,1,n)up(j,1,m){
			char now=getchars();
			if(now=='/')add((i-1)*m+j,i*m+j-1,0),add((i-1)*m+j-1,i*m+j,1),add(i*m+j-1,(i-1)*m+j,0),add(i*m+j,(i-1)*m+j-1,1);
			else add((i-1)*m+j,i*m+j-1,1),add((i-1)*m+j-1,i*m+j,0),add(i*m+j-1,(i-1)*m+j,1),add(i*m+j,(i-1)*m+j-1,0);
		}writeln(dijkstra(0,n*m-1));
		follower.ext();
	}
}signed main(){
	LC::main();
}
2024/7/3 16:09
加载中...