题目描述 Description 在有向图G中，每条边的长度均为1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件： 1．路径上的所有点的出边所指向的点都直接或间接与终点连通。 2．在满足条件1的情况下使路径最短。 注意：图G中可能存在重边和自环，题目保证终点没有出边。 请你输出符合条件的路径的长度。
输入描述 Input Description 第一行有两个用一个空格隔开的整数n和m，表示图有n个点和m条边。 接下来的m行每行2个整数x、y，之间用一个空格隔开，表示有一条边从点x指向点y。 最后一行有两个用一个空格隔开的整数s、t，表示起点为s，终点为t。
输出描述 Output Description 输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出-1。
样例 Sample Input1 3 2 1 2 2 1 1 3 Output1 -1
Input2 6 6 1 2 1 3 2 6 2 5 4 5 3 4 1 5 Output2 3
数据范围及提示 Data Size & Hint 对于30%的数据，0< n ≤10，0< m ≤20； 对于60%的数据，0< n ≤100，0< m ≤2000； 对于100%的数据，0< n ≤10,000，0< m ≤200,000，0< x,y,s,t≤n，x≠t。
题解：这个题的思想是先找到能走的点，然后跑最短路，由于边权都是1，所以可以用BFS来做。先反向建边跑一遍BFS，把能从终点到达的点标记出来，然后重新建边，从起点再跑一遍BFS找最短路。不要忘记把第一次BFS时用的数组清零。 PS：这题我偷懒想跑两遍spfa，然后。。。MDZZ
代码如下：
#include<queue> #include<cstdio> #include<cstring> #include<iostream> using namespace std; const int MAXE=200010; const int MAXV=10010; int first[MAXV],nxt[MAXE<<1],d[MAXV]; int x[MAXE<<1],y[MAXE<<1],a[MAXV]; bool used[MAXV]; int n,m,tot,s,t; struct edge { int from,to; }es[MAXE<<1]; void build(int f,int t) { es[++tot]=(edge){f,t}; nxt[tot]=first[f]; first[f]=tot; } void init1()//第一次bfs初始化 { memset(first,-1,sizeof(first)); memset(used,0,sizeof(used)); tot=0; } void init2()//第二次bfs初始化 { memset(first,-1,sizeof(first)); memset(es,0,sizeof(es)); memset(d,-1,sizeof(d)); memset(a,0,sizeof(a)); tot=0; } bool check(int ch)//检查一个点是否能走 { for(int i=first[ch];i!=-1;i=nxt[i]) { int v=es[i].to; if(!used[v]) return false; //只要这个点连着任何一个不与终点连通的点，这个点就不能用 } return true; } void bfs1()//第一次bfs { int ww=1,tt=0; a[1]=t; used[t]=1; while(ww>tt) { tt++; for(int i=first[a[tt]];i!=-1;i=nxt[i]) { int v=es[i].to; if(!used[v]) { ww++; a[ww]=v; used[v]=1;//标记一下能从终点到达的点 } } } } bool bfs2() { int ww=1,tt=0; d[s]=0; a[1]=s; while(ww>tt) { tt++; if(!check(a[tt])) continue;//如果当前点不能用直接continue for(int i=first[a[tt]];i!=-1;i=nxt[i]) { int v=es[i].to; if(d[v]==-1) { d[v]=d[a[tt]]+1; ww++; a[ww]=v; if(es[i].to==t) { printf("%d",d[v]); return true; } } } } return false; } int main() { scanf("%d%d",&n,&m); init1(); for(int i=1;i<=m;i++) { scanf("%d%d",&x[i],&y[i]); build(y[i],x[i]);//先反向建边 } scanf("%d%d",&s,&t); bfs1(); init2(); for(int i=1;i<=m;i++) build(x[i],y[i]);//正向建边，不要忘了初始化 if(!used[s]) { printf("-1\n"); return 0; } if(!bfs2()) printf("-1\n"); return 0; } /* 6 6 1 2 1 3 2 5 2 6 3 4 4 5 1 5 */