在有向图 GG 中，每条边的长度均为 11，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
注意：图 GG 中可能存在重边和自环，题目保证终点没有出边。
请你输出符合条件的路径的长度。
输入格式：
第一行有两个用一个空格隔开的整数 nn 和 mm，表示图有 nn 个点和 mm 条边。
接下来的 mm 行每行 22 个整数 x,yx,y，之间用一个空格隔开，表示有一条边从点 xx 指向点yy。
最后一行有两个用一个空格隔开的整数 s, ts,t，表示起点为 ss，终点为 tt。
输出格式：
————————————————————————————————————————————————————————
// luogu-judger-enable-o2 // luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f struct node{int nxt,to;}eg[200100]; int head[201000],ne,n,m,vist[200100],dis[201000],flag[200100],a,b,s,t; void adde(int f,int v){eg[++ne].to=v;eg[ne].nxt=head[f];head[f]=ne;} void spfa1(){ queue<int> q; for(int i=1;i<=n;i++) dis[i]=INF; q.push(t);dis[t]=0; vist[t]=1; while(!q.empty()){ int u=q.front(); q.pop();vist[u]=0; for(int i=head[u];i;i=eg[i].nxt) if(dis[eg[i].to]>dis[u]+1){ dis[eg[i].to]=dis[u]+1; if(vist[eg[i].to]==0){vist[eg[i].to]=1;q.push(eg[i].to);} } } } void spfa2(){ queue<int> q; for(int i=1; i<=n; i++) dis[i]=INF; q.push(t);dis[t]=0;vist[t]=1; while(!q.empty()){ int u=q.front(); q.pop();vist[u]=0; for(int i=head[u];i;i=eg[i].nxt) if(dis[eg[i].to]>dis[u]+1&&flag[eg[i].to]==0){ dis[eg[i].to]=dis[u]+1; if(vist[eg[i].to]==0){vist[eg[i].to]=1;q.push(eg[i].to);} } } } int main() { cin>>n>>m; for(int i=1;i<=m;i++) {cin>>a>>b;if(a==b)continue;adde(b,a);} cin>>s>>t; spfa1(); for(int i=1;i<=n;i++) if(dis[i]>=INF) for(int j=head[i];j;j=eg[j].nxt)flag[eg[j].to]=1; spfa2(); if(dis[s]>=INF)cout<<-1; else cout<<dis[s]; }
输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出-1−1。
原文：https://www.cnblogs.com/SFWR-YOU/p/10961192.html