两遍spfa，第一遍反向看有哪些点不联通，标记上，第二次正向spfa，标记了的点不能用来更新。

---

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 using namespace std; 8 const int maxn=1e4+5; 9 const int MAXN=2e5+5;10 const int inf=0x3f3f3f3f;11 int n,m,cnt,x[MAXN],y[MAXN],s,t,head[maxn],dis[maxn];12 bool vis[maxn],judge[maxn];13 struct edge{14 int v,nxt;15 }d[MAXN];16 queue 
           
             q;17 inline void add(int a,int b){18 d[++cnt].v=b;d[cnt].nxt=head[a];head[a]=cnt;19 }20 21 void spfa(int st){22 memset(vis,0,sizeof vis);23 memset(dis,63,sizeof dis);24 dis[st]=0;25 q.push(st);vis[st]=1;26 while(!q.empty()){27 int u=q.front();q.pop();vis[u]=1;28 for(int i=head[u];i;i=d[i].nxt){29 int v=d[i].v;30 if(judge[v])continue;31 if(dis[v]>dis[u]+1){32 dis[v]=dis[u]+1;33 if(!vis[v]){34 q.push(v);35 vis[v]=1;36 }37 }38 }39 }40 }41 42 int main(){43 scanf("%d%d",&n,&m);44 for(int i=1;i<=m;i++){45 scanf("%d%d",&x[i],&y[i]);46 add(y[i],x[i]);47 }48 scanf("%d%d",&s,&t);49 spfa(t);50 if(dis[s]==inf){51 printf("-1");52 return 0;53 }54 for(int i=1;i<=n;i++){55 if(dis[i]==inf){56 for(int j=head[i];j;j=d[j].nxt){57 judge[d[j].v]=1;58 }59 }60 }61 if(judge[s]==1){62 printf("-1");63 return 0;64 }65 cnt=0;memset(head,0,sizeof head);66 for(int i=1;i<=m;i++){67 add(x[i],y[i]);68 }69 spfa(s);70 if(dis[t]<=inf)printf("%d",dis[t]);71 else printf("-1");72 73 74 return 0;75 }