每天傍晚，約翰農夫都會搖響一口大鐘，召喚他的乳牛們回到牛棚吃晚餐。為了盡快趕到牛棚，它們都選擇走最短的路線。
農場由 N 塊田地（ 1 ≤ N ≤ 10,000 ）組成，方便編號為 1 . . . N ，穀倉位於 1 號田地。這些田地透過 $M$ 條雙向小徑（ N-1 ≤ M ≤ 50,000 ）連接。每條小徑都有對應的行程時間，每塊田地都可以通過某條小徑到達穀倉。
田地 i 中有 c_i 頭牛。聽到開飯鈴聲後，這些牛都會沿著一條耗時最短的路線走向牛棚。如果有多條路線耗時最短，牛會選擇其中「字典序」最小的路線（也就是說，如果兩條路線的路徑在字典序上相同，則優先選擇路徑索引較小的那條，例如，假設兩條路線的通行時間相同，則訪問田地 7、3、6、1 的路徑優於訪問田地 7、5、1 的路徑）。
農夫約翰擔心牛棚離一些田地太遠。他把每頭牛的行走時間加起來，所有牛的行走時間加起來，這個數字就是總行走時間。他想盡可能地縮短這個數字，於是增加了一條從牛棚（田地 1）到他選擇的另一塊田地的“捷徑”，這條捷徑的行走時間為 T ( 1 ≤ T ≤ 10,000 )。如果一頭牛在去牛棚的路上偶然發現了這條捷徑，而捷徑能讓她更快到達牛棚，她就會走捷徑。否則，即使捷徑可以縮短行走時間，她也會繼續走她平常的路線。
請幫助農夫約翰確定，如果他建造一條捷徑，他的總旅行時間最多可以減少多少。
輸入的第一行包含 N 、 M 和 T 。下一行包含 N 個整數 c_1 . . . c_N ，每個整數的取值範圍為 0 . . . 10,000 。接下來的 M 行分別使用三個整數 a 、 b 和 t 來描述一條路徑，該路徑連接 a 和 b 兩個字段，行程時間為 t 。所有行程時間的取值範圍均為 1 . . . 25,000 。
請計算農夫約翰能夠實現的最大旅行時間縮減量。
5 6 2 1 2 3 4 5 1 2 5 1 3 3 2 4 3 3 4 5 4 5 2 3 5 7
40
不公開 測資點#0 (5%): 0.1s , <1M
不公開 測資點#1 (5%): 0.1s , <1M
不公開 測資點#2 (5%): 0.1s , <1M
不公開 測資點#3 (5%): 0.1s , <1M
不公開 測資點#4 (5%): 0.1s , <1M
不公開 測資點#5 (5%): 0.1s , <1M
不公開 測資點#6 (5%): 0.1s , <1M
不公開 測資點#7 (5%): 0.1s , <1M
不公開 測資點#8 (5%): 0.1s , <1M
不公開 測資點#9 (5%): 0.1s , <1M
不公開 測資點#10 (5%): 0.1s , <1M
不公開 測資點#11 (5%): 0.1s , <1M
不公開 測資點#12 (5%): 0.1s , <1M
不公開 測資點#13 (5%): 0.1s , <1M
不公開 測資點#14 (5%): 0.1s , <1M
不公開 測資點#15 (5%): 0.1s , <1M
不公開 測資點#16 (5%): 0.1s , <1M
不公開 測資點#17 (5%): 0.1s , <1M
不公開 測資點#18 (5%): 0.1s , <1M
不公開 測資點#19 (5%): 0.1s , <1M
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||