BFS 尋找道路

題目:

在有向圖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

 

關鍵詞:lt int gt 終點 路徑 node head nx bfs vis

相關推薦:

博客作業06--圖

尋找道路(無權有特殊條件最短路)

CodeForces - 540C Ice Cave —— BFS

HDU 1043 八數碼問題 BFS + 康拓 (經典搜索題)

HDU 3533 Escape BFS

Japan 2005 Domestic Cleaning Robot /// BFS 狀壓 二進制位運算 結構體內構造函數 oj22912

NOIP TG 2014 尋找道路 【SPFA】

迷宮問題初級(bfs+隊列)

POJ3026 Borg Maze(bfs求邊+最小生成樹)

P2491 [SDOI2011]消防