TopCoder

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

50.0% (6/12)

Tags

Description

充滿戰亂的福文大地上共有 N 座城市,城市之間共有 M 條雙向道路。
每次經過一條道路,就會被駐守在該地的聯盟軍攻擊,損失 Ci 的血量。
同時每經過一座城市,就會被收取 fi 的過路費 (包括起點和終點)。

小晨攜帶著蒂瑪西亞人民的希望,從城市 1 出發,要穿越重重危險到達城市 N 尋求戰力支援。
出發時小晨的血量為 H ,請你考慮所有血量不降到負數且到達城市 N 的的路線中,能最小化路線上「最多的那次城市過路費」的路線並輸出該費用。
如果無論如何小晨都無法順利到達城市 N,請你輸出 1

Input Format

第一行包含三個正整數 N, M, H 以空白隔開,代表有 N 座城市,有 M 條道路,小晨的血量為 H
接下來有 n 行,每行一個正整數 fi,表示經過城市 i 會被收取 fi 的過路費。
再接下來有 m 行,每行有三個正整數 a, b, c 以空白隔開,代表城市 a 和城市 b 之間有一條道路。如果從城市 a 到城市 b,或者從城市 b 到城市 a 會損失 c 的血量。

  • N104
  • M5×104
  • 1a,bNab
  • H,c,fi109

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

Sample Output 1

10

Hints

Problem Source

洛谷 - P1462

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
24 1000 524288 65536 2
25 1000 524288 65536 2
26 1000 524288 65536 2
27 1000 524288 65536 2
28 1000 524288 65536 2
29 1000 524288 65536 2
30 1000 524288 65536 2
31 1000 524288 65536 2
32 1000 524288 65536 2
33 1000 524288 65536 2
34 1000 524288 65536 2
35 1000 524288 65536 2
36 1000 524288 65536 2
37 1000 524288 65536 2
38 1000 524288 65536 2