分層圖最短路即可

#include
    
     using namespace std;#define N 1000010int n,m,v[N*2],nxt[N*2],w[N*2],h[N],ec,d[N],vis[N],s,t,x[N],y[N],sx,sy,tx,ty;void add(int x,int y,int z){v[++ec]=y;w[ec]=z;nxt[ec]=h[x];h[x]=ec;}void bfs(){	queue
     
      q;	q.push(s);	vis[s]=1;	memset(d,63,sizeof(d));	d[s]=0;	while(!q.empty()){		int x=q.front();		q.pop();		vis[x]=0;		for(int i=h[x];i;i=nxt[i])			if(d[v[i]]>d[x]+w[i]){				d[v[i]]=d[x]+w[i];				if(!vis[v[i]]){					vis[v[i]]=1;					q.push(v[i]);				}			}	}}bool c1(int a,int b){return y[a]