TopCoder

1xlc

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

37.5% (3/8)

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

Sample Output 1

Sample Input 2

3 2
1 2 1
2 1 1
1 2

Sample Output 2

Hints

Problem Source

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

776 . 有向圖最短路