Sicily shortest path in unweighted graph，sicilyunweighted

Sicily shortest path in unweighted graph，sicilyunweighted

題目介紹：

輸入一個無向圖，指定一個頂點s開始bfs遍歷，求出s到圖中每個點的最短距離。

如果不存在s到t的路徑，則記s到t的距離為-1。   Input

輸入的第一行包含兩個整數n和m，n是圖的頂點數，m是邊數。1<=n<=1000，0<=m<=10000。

以下m行，每行是一個數對v y，表示存在邊(v,y)。頂點編號從1開始。    Output

記s=1，在一行中依次輸出：頂點1到s的最短距離，頂點2到s的最短距離，...，頂點n到s的最短距離。

每項輸出之後加一個空格，包括最後一項。   Sample Input

5 3
1 2
1 3
2 4

Sample Output

0 1 1 2 -1 

思路：

     利用廣度搜索，標記層數，依次計算距離即可。

     具體代碼如下：

 1 #include <iostream>
 2 #include <queue>
 3 using namespace std;
 4 
 5 bool path[1001][1001];
 6 int shortest[1001];
 7 
 8 int main() {
 9     int n, m;
10     cin >> n >> m;
11     
12     for (int i = 1; i <= m; i++) {
13         int node1, node2;
14         cin >> node1 >> node2;
15         path[node1][node2] = true;
16         path[node2][node1] = true;
17     }
18     
19     for (int i = 1; i <= n; i++)
20         i == 1 ? shortest[i] = 0 : shortest[i] = -1;
21     
22     int distance = 0;
23     queue<int> store;
24     store.push(1);
25     while (!store.empty()) {
26         int size = store.size();
27         distance++;
28         while (size--) {
29             for (int i = 1; i <= n; i++) {
30                 if (path[store.front()][i] && shortest[i] == -1) {
31                     shortest[i] = distance;
32                     store.push(i);
33                 }
34             }
35             store.pop();
36         }
37     }
38     
39     for (int i = 1; i <= n; i++)
40         cout << shortest[i] << " ";
41     cout << endl;
42     
43     return 0;
44 }