1572 . 最短路線問題(Path)
TopCoder
Tags
Description
給你一份地圖，地圖上標有許多城市，編號為1~n。
此外，某些城市之間有雙向的聯絡道路，現在請問從某個城市A開始，到達另一個城市B，路途中最少需要經過幾個城市呢？
你能不能把它列出來？ 如果有多條路線可以經過最少的城市到達城市B，那麼我們會選擇「字典順序最小」的那條。
也就是說，如果把經過的城市依序寫出來，並且依序代表n+1進位的每一位數，那麼請輸出最小的那個數所對應的那條路線。
例如1-3-4-5與1-2-3-5，我們會優先考慮1-2-3-5。
噢對了，這個地圖上任何兩個城市之間至少有一條路線連通。
Input Format
第一列有四個正整數n, m, A, B (1<= A, B<=n，A和B相異)，其中n代表有n個城市，m代表有m條聯絡道路。
接下來有m條道路的資訊：第i列有兩個數字Xi,Yi代表第i條道路來往於Xi和Yi兩個城市
Output Format
第一列請輸出從A到B所需要經過的最少城市數量。
第二列請輸出從A到B字典順序最小的最短路線。
Sample Input 1
範例輸入1
5 5 1 2
1 3
3 4
4 5
5 2
3 5
範例輸入2
5 5 2 5
1 2
2 3
3 4
4 5
5 1
5 5 1 2
1 3
3 4
4 5
5 2
3 5
範例輸入2
5 5 2 5
1 2
2 3
3 4
4 5
5 1
Sample Output 1
範例輸出1
2
1-3-5-2
範例輸出2
1
2-1-5
2
1-3-5-2
範例輸出2
1
2-1-5
Hints
佔總分30%的測試資料中，1<=n, m<=10。
佔總分60%的測試資料中，1<=n, m<=700。
對於全部的測試資料而言，1<=n, m<= 1,000,000。
Problem Source
原TIOJ1572 / 97建中校內資訊能力競賽(prob3)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |