首先将边反向建立，然后bfs求出答案
1 #include<bits/stdc++.h> 2 using namespace std; 3 int read() 4 { 5 int x=0,y=1;char c=getchar(); 6 while(c>'9'||c<'0'){if(c=='0')y=-1;c=getchar();} 7 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 8 return x*y; 9 } 10 int n,m; 11 vector<int>v[10005]; 12 bool cando[10005],er[10005]; 13 queue<int>q; 14 int st,ed; 15 int ans[10005]; 16 int main() 17 { 18 n=read(),m=read(); 19 for(int i=1;i<=m;i++) 20 { 21 int a=read(),b=read(); 22 if(a==b)continue;//去除自环 23 v[b].push_back(a); 24 } 25 st=read(),ed=read(); 26 cando[ed]=1;//第一遍bfs 27 q.push(ed); 28 while(!q.empty()) 29 { 30 int no=q.front(); 31 q.pop(); 32 for(int i=0,j=v[no].size();i<j;i++) 33 if(!cando[v[no][i]]){cando[v[no][i]]=1;q.push(v[no][i]);}//标记从终点可以到达的点 34 } 35 memcpy(er,cando,sizeof(cando));//准备第二次标记 36 //注意这里最好有第二个数组标记，在一个数组里删点有后效型，如果一个点开始被标记，它通过一个序号比它小的点删除了， 37 //那么访问到它的时候，就会被当成开始就没被标记的点，会通过它把合法点删除。 38 //这样做完之后，合法点都被标记了。 39 for(int i=1;i<=n;i++) 40 if(!cando[i]) 41 for(int j=0,k=v[i].size();j<k;j++) 42 if(er[v[i][j]]) 43 er[v[i][j]]=0; 44 //最后一遍bfs找答案。 45 q.push(ed); 46 while(!q.empty()) 47 { 48 int no=q.front(); 49 q.pop(); 50 for(int i=0,j=v[no].size();i<j;i++) 51 if(er[v[no][i]]) 52 { 53 q.push(v[no][i]); 54 er[v[no][i]]=0; 55 ans[v[no][i]]=ans[no]+1; 56 } 57 } 58 //题目要求输出。 59 if(ans[st]==0)printf("-1"); 60 else printf("%d",ans[st]); 61 return 0; 62 }