TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

100.0% (38/38)

Submission's AC Ratio

40.0% (72/180)

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

Sample Output 1

33
-1

Hints

第一組測資最短是11
第二短距離不是長度35的0-2-1,而是長度33的0-1-0-1

Problem Source

原TIOJ1561 / 2009雄中公假社

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1