779 . 穿越福文大地
TopCoder
Tags
Description
充滿戰亂的福文大地上共有 $N$ 座城市，城市之間共有 $M$ 條雙向道路。
每次經過一條道路，就會被駐守在該地的聯盟軍攻擊，損失 $C_i$ 的血量。
同時每經過一座城市，就會被收取 $f_i$ 的過路費 （包括起點和終點）。
小晨攜帶著蒂瑪西亞人民的希望，從城市 $1$ 出發，要穿越重重危險到達城市 $N$ 尋求戰力支援。
出發時小晨的血量為 $H$ ，請你考慮所有血量不降到負數且到達城市 $N$ 的的路線中，能最小化路線上「最多的那次城市過路費」的路線並輸出該費用。
如果無論如何小晨都無法順利到達城市 $N$，請你輸出 $-1$。
Input Format
第一行包含三個正整數 $N$, $M$, $H$ 以空白隔開，代表有 $N$ 座城市，有 $M$ 條道路，小晨的血量為 $H$。
接下來有 $n$ 行，每行一個正整數 $f_i$，表示經過城市 $i$ 會被收取 $f_i$ 的過路費。
再接下來有 $m$ 行，每行有三個正整數 $a$, $b$, $c$ 以空白隔開，代表城市 $a$ 和城市 $b$ 之間有一條道路。如果從城市 $a$ 到城市 $b$，或者從城市 $b$ 到城市 $a$ 會損失 $c$ 的血量。
- $N \le 10^ 4$
- $M \le 5\times 10^ 4$
- $1 \le a,b \le N$ 且 $a \neq b$
- $H,c,f_i \le 10^ 9$
Output Format
輸出一個整數代表所經過的所有城市中「最多的那次城市過路費」的最小值
如果無法抵達，請輸出 $-1$。
Sample Input 1
4 4 8
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3
Sample Output 1
10
Hints
Problem Source
洛谷 - P1462
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~38 | 無額外限制 | 100 |