a275. TOI 2025/04 潛力組：供給調度

題目描述

N 個倉庫以 M 條可雙向通行的路線連接，每條路線有維護成本。可以選擇保留部分路線，但必須使任何兩個倉庫仍能互相到達。最佳營運成本是所有合法保留方案中的最小成本總和。

接著依序發生 Q 次調價，每次把一條既有路線的成本增加指定數值，所有調價累積生效。請找出最佳營運成本首次嚴格超過 K 的時機。

輸入格式

第一行有 N、M、Q。接著 M 行各有 S、T、C，表示一條路線及其初始成本；接著 Q 行各有 Qs、Qt、Qc，表示將該路線成本增加 Qc。最後一行為 K。

• 3 ≤ N ≤ 10000，2 ≤ M ≤ 10000，1 ≤ Q ≤ 100000
• 路線端點滿足 0 ≤ S < T < N，調價端點亦同，指定路線皆存在
• 路線不重複，原圖連通
• 1 ≤ C ≤ 100000，1 ≤ Qc ≤ 100，1 ≤ K ≤ 10⁹

輸出格式

輸出首次超過 K 時已發生的調價次數。如果初始成本就超過 K，輸出 0；如果全部調價後仍未超過 K，輸出 −1。

來源

TOI 2025 年 4 月潛力組〈供給調度〉。本敘述重新撰寫；範例與測資為另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202504/Supply.pdf