a125. TOI 2022/05 潛力組：加油

題目描述

有 N 座城市與 M 條雙向道路。你要從城市 1 開車到城市 N。油箱容量為 F 公升，出發時已加滿，每走 1 公里消耗 1 公升。

到達中途城市 i 時，可以選擇花 ti 分鐘等待加油，將油量補回 F；也可以不加油繼續走。道路上不能加油，但允許剛好用完油時抵達下一座城市。

請規劃路線與加油地點，使能夠到達城市 N 且加油等待時間總和最少。行車時間不計入目標。

輸入格式

第一行輸入 N、M、F，3 ≤ N ≤ 200，1 ≤ M ≤ N(N−1)/2，1 ≤ F ≤ 1000000。 第二行有 N−2 個整數，依序為 t2 到 tN−1，1 ≤ ti ≤ 1000。 接下來 M 行各有 a、b、c，表示城市 a 與 b 間有長度 c 的道路，其中 1 ≤ a < b ≤ N，1 ≤ c ≤ F。 同一對城市間不會有重複道路，圖不一定連通。

輸出格式

若能到達城市 N，輸出最少加油等待分鐘數；否則輸出 -1。

來源

TOI 2022 年 5 月潛力組〈加油〉。依官方題意重新撰寫，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202205/Refueling.pdf