TopCoder

Caido
Waimai

User's AC Ratio

94.4% (17/18)

Submission's AC Ratio

33.3% (29/87)

Tags

Description

小祥平時的工作是在樂團裡彈鋼琴,但是彈琴賺的錢不夠多,除了在客服打工還有陪初華散步外,小祥會當 F1 的賽車手,小祥的賽車叫阿倍姆基。

因為小祥樓樓上的鄰居是從昨天開始才看 F1,所以小祥要講解 F1 賽車的規則:有 N 個站點與 M 條雙向賽道,每條雙向賽道連接兩個站點 ui,vi,並且長度為 wi 公里。所有站點是連通的,代表任兩個站點可以經過一系列賽道到達。

小祥要從站點 1 開她的賽車阿倍姆基到站點 N,她會攜帶 L 罐氮氣,每罐氮氣會有一個係數 ai,代表用了這罐氮氣後賽車 1 公里只要開 ai 秒。小祥會從第 1 罐氮氣依序往後使用,每次要經過一個賽道時,假設目前用完 k1 罐氮氣輪到第 k 罐氮氣,小祥可以做以下的動作:丟掉 p0p) 罐氮氣,並使用目前的氮氣 ak+p 開過賽道,一罐氮氣在開完一個賽道後就會消耗完畢,下一次使用時會從 ak+p+1 開始看。如果過程中不在站點 N 且已經用完 L 罐氮氣了,代表阿倍姆基卡在原地,小祥會被罰錢,為了不讓小祥被罰錢,N1L,代表小祥在不丟掉氮氣的情況下,可以從站點 1 開到站點 N

小祥的成績計算方式是開過的賽道裡花的時間最久的那個,也就是假設小祥在從站點 1 開到站點 N 的過程中開過了 S 條賽道,編號分別是 x1xS,使用氮氣的編號分別是 y1yS,那她的成績會是 maxi=1S(wxiayi)
為了贏過東京阿儂大車隊,小祥想要成績越小越好,請你幫幫她算出最小可以是多少!

Input Format

第一行會有兩個整數 N, M, L
第二行會有 L 個整數 a1aL
接下來 M 行,第 i 行會輸入三個正整數 ui,vi,wi

對於所有測試資料:

  • 2N105
  • N1M105
  • N1L3×105
  • 1ai109
  • 1ui,viN
  • 1wi109
  • 保證輸入是一張簡單連通圖

Output Format

輸出一個整數代表小祥的成績最小是多少。

Sample Input 1

4 4 6
1 1 1 1 1 1
1 2 2
2 3 3
1 3 4
3 4 5

Sample Output 1

5

Sample Input 2

10 9 15
14 45 132 43 12 31 43 12 1 34 12 3 12 8 12
1 2 22
2 3 34
3 4 48763
4 5 241
5 6 234
6 7 45
7 8 43
8 9 123
9 10 134

Sample Output 2

48763

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0, 2~6 ai=1 7
3 0, 2~11, 47 aiai+1 遞減 14
4 1, 12~16, 47 輸入的圖為一條鏈,M=N1,ui=i.vi=i+1 21
5 0~1, 17~21, 47 N,M,L3000 11
6 0~1, 17~26, 47 N,M3000 17
7 0~47 無其他限制 30

Testdata and Limits

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