TopCoder

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

37.5% (3/8)

Tags

Description

現在有一張 N 個點 M 條邊的有向圖,代表有 N 個城市 ( 編號 1N ), 由 M 條有向道路連接 ( 城市之間有可能不連通,無法抵達 )。
每條道路都有各自的長度。請你設計一份程式計算從城市 S 出發抵達城市 T 的最短路徑。若無法抵達,請輸出 1

Input Format

第一行包含兩個正整數 N, M 以空白隔開,代表有 N 座城市,有 M 條道路
2 行至第 M+1 行,每行有三個正整數 a, b, c 以空白隔開,代表城市 a 有一條長度為 c 的單向道路通往城市 b
M+2 行包含兩個正整數 S, T

  • 1N105
  • 1M105
  • 1a,b,S,TNab
  • 1c109

Output Format

輸出 1 個正整數代表從城市 S 出發抵達城市 T 的最短路徑長度。若無法抵達,請輸出 1

Sample Input 1

10 11
1 2 6
2 3 1
3 4 1
4 5 4
5 6 10
6 2 5
7 6 8
5 8 2
3 9 1
9 10 1
10 4 1
1 8

Sample Output 1

14

Sample Input 2

3 2
1 2 1
2 1 1
1 2

Sample Output 2

1

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~17 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 800 524288 65536 1 2
1 800 524288 65536 1 2
2 800 524288 65536 2
3 800 524288 65536 2
4 800 524288 65536 2
5 800 524288 65536 2
6 800 524288 65536 2
7 800 524288 65536 2
8 800 524288 65536 2
9 800 524288 65536 2
10 800 524288 65536 2
11 800 524288 65536 2
12 800 524288 65536 2
13 800 524288 65536 2
14 800 524288 65536 2
15 800 524288 65536 2
16 800 524288 65536 2
17 800 524288 65536 2