在有向图G中,每条边的长度均为1,现给定起点和终点,请你在图中找一条从起点到终点的路径,
该路径满足以下条件:
1.路径上的所有点的出边所指向的点都直接或间接与终点连通。
2.在满足条件1的情况下使路径最短。
注意:图G中可能存在重边和自环,题目保证终点没有出边。
请你输出符合条件的路径的长度。
输入描述:
第一行有两个用一个空格隔开的整数n和m,表示图有n个点和m条边。 接下来的m行每行2个整数x、y,之间用一个空格隔开,表示
有一条边从点x指向点y。最后一行有两个用一个空格隔开的整数s、t,表示起点为s,终点为t。
输出描述:
输出只有一行,包含一个整数,表示满足题目描述的最短路径的长度。如果这样的路径不存在,输出-1。
示例1
输入
复制
3 2
1 2
2 1
1 3
输出
复制
-1
说明
如上图所示,箭头表示有向道路,圆点表示城市。起点1与终点3不连通,所以满足题目描述的路径不存在,故输出-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