776 . 有向圖最短路
TopCoder
Tags
Description
現在有一張 $N$ 個點 $M$ 條邊的有向圖，代表有 $N$ 個城市 ( 編號 $1$ 到 $N$ )， 由 $M$ 條有向道路連接 ( 城市之間有可能不連通，無法抵達 )。
每條道路都有各自的長度。請你設計一份程式計算從城市 $S$ 出發抵達城市 $T$ 的最短路徑。若無法抵達，請輸出 $-1$。
Input Format
第一行包含兩個正整數 $N$, $M$ 以空白隔開，代表有 $N$ 座城市，有 $M$ 條道路
第 $2$ 行至第 $M+1$ 行，每行有三個正整數 $a$, $b$, $c$ 以空白隔開，代表城市 $a$ 有一條長度為 $c$ 的單向道路通往城市 $b$。
第 $M+2$ 行包含兩個正整數 $S$, $T$
- $1 \le N \le 10^ 5$
- $1 \le M \le 10^ 5$
- $1 \le a,b,S,T \le N$ 且 $a \neq b$
- $1 \le c \le 10^ 9$
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
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
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 |