754 . 旅遊優惠券
TopCoder
Tags
Description
皮皮經常穿梭世界各地，也因此他拿到了航空公司的優惠券，可以免費搭乘一趟飛機。假設世界上一共有 $N$ 個編號 $1\sim N$ 的城市以及 $M$ 條票價不盡相同的航線。皮皮想要從 $S$ 城市出發到 $T$ 城市，中間可能要經過幾趟轉機才能到達，但是免費優惠券只能用在途中的一條航班上，而其他航班仍須正常收費。請問皮皮的最小花費為何。
Input Format
輸入第一行是四個空白分隔的整數 $N, M, S, T$，分別代表城市數量，航班數量，以及起點和終點城市。
接下來有 $M$ 行每行三個空白分隔的整數 $u,v,w$，分別代表航班起點和終點，以及票價。特別注意航班都是單向的。
輸入保證 $2\le N\le 10^ 5$，$1\le M\le 10^ 5$，$1\le w\le 10^ 9$，$1\le S, T, u, v\le N$，$S\ne T$，$u\ne v$，以及沒有兩個航班有相同起終點。
Output Format
輸出一行一個整數表示皮皮的最小花費。如果皮皮無法用提供的航班抵達 $T$ 城市，請輸出 $-1$。
Sample Input 1
4 5 1 4
1 2 7
2 3 5
1 3 8
3 4 9
2 4 10
1 2 7
2 3 5
1 3 8
3 4 9
2 4 10
Sample Output 1
7
Sample Input 2
3 1 1 3
1 2 5
1 2 5
Sample Output 2
-1
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~14 | 無額外限制 | 100 |