这道题具有很大的思维价值,所以我做了好多遍。
这道题与其他最短路问题最不一样的地方就在于一个条件:路径上的所有点的出边所指向的点都直接或间接与终点连通。
那我们思考如何才能得出符合这个条件的点:
考虑这三个点集:1.所有的点 2.所有与终点连通的点 3.所有该点的出边所指向的点都与终点连通的点
不难发现,第三个集合是符合条件的,而且我们知道如何从1筛到2(反向建边+bfs),再从2筛到3(模拟判断),那么这道题我们就做完了。
注:因为边权都为1,所以bfs即可计算单源最短路,并不需要dijkstra和SPFA
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define int long long #define maxn 200010 #define rep(i,s,e) for(register int i=s;i<=e;++i) #define dwn(i,s,e) for(register int i=s;i>=e;--i) using namespace std; inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9') {x=x*10+c-'0'; c=getchar();} return f*x; } inline void write(int x) { if(x<0){putchar('-');x=-x;} if(x>9)write(x/10); putchar(x%10+'0'); } int n,m,s,t; int cnt1,cnt2,flag; int head1[maxn],head2[maxn],book1[maxn],book2[maxn],mark[maxn]; struct node1 { int v,nex; }edge1[maxn]; struct node2 { int v,nex; }edge2[maxn]; inline void add1(int x,int y) { edge1[++cnt1].v=y; edge1[cnt1].nex=head1[x]; head1[x]=cnt1; } inline void add2(int x,int y) { edge2[++cnt2].v=y; edge2[cnt2].nex=head2[x]; head2[x]=cnt2; } void bfs_back(int st) { queue<int> q; q.push(st); book1[st]=1; while(!q.empty()) { int from=q.front(); q.pop(); for(int i=head1[from];i;i=edge1[i].nex) { int to=edge1[i].v; if(book1[to]==1) continue; book1[to]=1; q.push(to); } } } int bfs_front(int st) { queue<pair<int,int> > q; q.push(make_pair(st,0)); book2[st]=1; while(!q.empty()) { int from=q.front().first,step=q.front().second; q.pop(); if(from==t) { flag=1; return step; } for(int i=head2[from];i;i=edge2[i].nex) { int to=edge2[i].v; if(book2[to]==1||mark[to]==0) continue; book2[to]=1; q.push(make_pair(to,step+1)); } } if(flag==0) return -1; } signed main() { n=read();m=read(); rep(i,1,m) { int x=read(),y=read(); add1(y,x); add2(x,y); } s=read();t=read(); bfs_back(t); if(book1[s]==0) { write(-1); return 0; } rep(i,1,n) { if(book1[i]==1) { mark[i]=1; int from=i; for(int j=head2[from];j;j=edge2[j].nex) { int to=edge2[j].v; if(book1[to]==0) { mark[from]=0; break; } } } } int ans=bfs_front(s); write(ans); return 0; }