1561 . 改變路線
TopCoder
Tags
Description
某G上學總是騎腳踏車(卡打車是用釣的不是用騎的(？))。
某一天上學時，他發現離學校最近的路線總是塞車，所以他打算找另外一條道路，學電腦科學的他自然的會想要找一條第二短路徑。於是他實地去量每一段道路的長度。
不過為了走第二短路徑，他也許會同一條路來回走很多次，好像不走第二短的路徑就會塞車塞到康(？)。
Input Format
第一列有n,m，代表現在地圖上有n(1<=n<=100)個點(編號0~n-1)，有m條量好的路的長度，接下來的m列，每列都有三個數字a,b,d，代表從編號a到編號b的道路長為d(1<=d<=100)。
接下來有兩個數st,ed，代表G家的編號和學校的編號。
Output Format
印出從G家到學校的第二短路徑，若不存在則輸出-1。
Sample Input 1
3 3
0 1 11
0 2 20
1 2 15
0 1
4 3
0 1 12
0 2 20
1 2 15
0 3
0 1 11
0 2 20
1 2 15
0 1
4 3
0 1 12
0 2 20
1 2 15
0 3
Sample Output 1
33
-1
-1
Hints
第一組測資最短是11
第二短距離不是長度35的0-2-1，而是長度33的0-1-0-1
Problem Source
原TIOJ1561 / 2009雄中公假社
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |