a118. TOI 2019/11 潛力組：潛水

題目描述

N 座島之間有 M 條可雙向通行的潛水路徑。每條路徑需要消耗指定氧氣量；抵達任何島後都能把氧氣筒補滿。請求出由 A 島到 B 島所需的最小氧氣筒容量。

輸入格式

第一行為 N、M，接著 M 行各有 u、v、W，表示兩島之間的氧氣需求。最後一行為 A、B。 2 ≤ N ≤ 500；0 ≤ M ≤ N(N−1)/2；島嶼編號為 0 到 N−1；2 ≤ W ≤ 50000。

輸出格式

輸出最小容量；無法到達時輸出 −1。若出發與目的相同，不需消耗氧氣。

來源

TOI 2019/11/25~2019/11/29 潛力組〈潛水〉。本題以自寫文字重述規則，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/201911/A2-Diving.pdf