BFS 寻找道路
在有向图G中，每条边的长度均为1，现给定起点和终点，请你在图中找一条从起点到终点的路径，
该路径满足以下条件：
1．路径上的所有点的出边所指向的点都直接或间接与终点连通。
2．在满足条件1的情况下使路径最短。
注意：图G中可能存在重边和自环，题目保证终点没有出边。
请你输出符合条件的路径的长度。
输入描述:
第一行有两个用一个空格隔开的整数n和m，表示图有n个点和m条边。 接下来的m行每行2个整数x、y，之间用一个空格隔开，表示
有一条边从点x指向点y。最后一行有两个用一个空格隔开的整数s、t，表示起点为s，终点为t。
输出描述:
输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出-1。
示例2
输入
6 6 1 2 1 3 2 6 2 5 4 5 3 4 1 5
输出
3
说明
如上图所示，满足条件的路径为1->3->4->5。注意点2不能在答案路径中，因为点2连了一条边到点6，而点6不与终点5连通。
备注:
对于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。
解析：
这题题目虽然聊聊几句，但第一个条件我是看了样例才懂什么意思~~路径上的所有点相连的边的边都要通向
终点。那么思路就来了，先反向建图，反向遍历（这样，能通向终点的点都会走过，而不可以的点则不会走过，
将样例二的箭头都反过来就更一目然了），用一个数组vis来标记到达过的点。之后，可以将图重新正向建立，
（注意vis数组仍然保留），再正向遍历之，跳过之前反向遍历没有到达过的点，找到最短路径即可。
存图，个人喜欢用链式向前星（真的很好用ヾ(◍°∇°◍)ﾉﾞ），不懂得可以百度下，我博客之后也会有，
存图一定要理解，不然使用搜索的算法时会很乱。接着最短路径就直接bfs和queue的最佳组合，因为都是正
权，所以spfa就没必要啦~
代码走起，个人有注释习惯，不用担心naked令人窒息的代码~
转载注明出处，谢谢！
1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 using namespace std; 5 const int maxn=2000005; 6 struct Node{//链式向前星处理 7 int from,to; //权值都为1，不必再写 8 int next; 9 } node[maxn]={0}; 10 int head[maxn]={0},dis[10005]={0}; 11 bool vis[maxn]={0}; 12 int cnt=0,n=0,m=0,st=0,en=0; 13 void addnode(int from,int to) 14 { 15 node[cnt].next=head[from]; 16 node[cnt].to=to; 17 head[from]=cnt++; //链式向前星存图 18 } 19 bool bfs0() //反向搜索,标记所有连通点 20 { 21 queue<int> q; 22 q.push(en);//起点为终点 23 vis[en]=true; 24 while(!q.empty())//遍历所有与终点连通的点，并标记 25 { 26 int x=q.front(); 27 q.pop(); 28 for(int i=head[x];i!=-1;i=node[i].next) 29 {//点的各个方向遍历 30 int nx=node[i].to; 31 if(!vis[nx]){ 32 vis[nx]=true; 33 q.push(nx); 34 } 35 } 36 } 37 if(vis[st]){//能够到达起点 38 return true; 39 } 40 return false;//无法到达 41 } 42 bool Check(int pos)//判断是否各方向与终点连通 43 { 44 for(int i=head[pos];i!=-1;i=node[i].next) 45 {//该点的各方向遍历 46 if(!vis[node[i].to]) return false; 47 } 48 return true; 49 } 50 void bfs1() //正向再遍历，排除有不连通点的边，再找最短路径 51 {//距离初始为零 52 queue<int> q; 53 q.push(st); 54 dis[st]=0; 55 while(!q.empty()) 56 { 57 int x=q.front(); 58 q.pop(); 59 if(!Check(x)) continue;//该点不符合各出边与终点连通 60 for(int i=head[x];i!=-1;i=node[i].next) 61 { 62 int nx=node[i].to; 63 if(dis[nx]==-1){//初次到达,根据bfs的特性，必是最短 64 dis[nx]=dis[x]+1; 65 if(nx==en){//到达终点 66 cout<<dis[nx]<<endl; 67 return; 68 } 69 q.push(nx); 70 } 71 }//各方向遍历完 72 } 73 cout<<-1<<endl; 74 return ; 75 } 76 int x[maxn]={0},y[maxn]={0}; 77 int main() 78 { 79 ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);//解绑，提高输入输出效率 80 memset(head,-1,sizeof(head)); 81 cin>>n>>m; 82 for(int i=0;i<m;++i) 83 { 84 cin>>x[i]>>y[i]; 85 addnode(y[i],x[i]); //反向建图 86 } 87 cin>>st>>en; 88 if(!bfs0()){//无法到达 89 cout<<-1<<endl; 90 return 0; 91 } 92 memset(head,-1,sizeof(head)); 93 memset(node,0,sizeof(node));//清空,重新建图,vis保留辅助判断 94 memset(dis,-1,sizeof(dis)); 95 for(int i=0;i<m;++i) 96 addnode(x[i],y[i]); 97 bfs1(); 98 return 0; 99 }
View Code
版权声明：本文为GorgeousBankarian原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。