e810.
2.潛水 (Diving)
內容
TOI練習賽_2019/11_a2.潛力組2.潛水 (Diving) {試題連結}
問題敘述
小軒是一個熱愛潛水的人，他趁著放暑假的時間去澎湖潛水。澎湖由許多小 島組成，小軒今天想從 A 島經由潛水的方式到 B 島。潛水需要背著氧氣筒，而 小軒不想浪費力氣去背過重的氧氣筒，他希望氧氣筒的容量夠用就好。小島間的 距離有長有短，需要花費的氧氣量也不同，但有些島之間不能由潛水來移動；每 抵達一座島就可以把氧氣筒重新裝滿。請你幫小軒算出他最少要背多少容量的氧 氣筒才能讓他順利從 A 島潛水抵達 B 島。
輸入說明
第一列有兩個整數 N 與 M（2<=N<=500、0<=M <= N(N-1)/2），代表有 N 座小 島以及 M 條潛水路徑，小島的編號為 0～N－1。接下去有 M 列，代表島與島之 間移動所需花費的氧氣量；每列有三個整數，前兩個整數為島的編號，第三個整 數為兩個島之間潛水移動需要的氧氣量 W (2 <=W <=50000)，雙向所需要的氧氣量 相等。最後一列有兩個整數 A 與 B，代表小軒想從 A 島潛水移動到 B 島。
輸出說明
請輸出小軒最少要背多少容量的氧氣筒，若從 A 島無法經由潛水移動到 B 島，請輸出 -1。
範例輸入
#1
4 4 0 2 3 0 1 1 1 3 6 2 3 5 0 3
範例輸出
#1
5
範例輸入
#2
5 6 0 1 1 0 2 2 1 3 4 3 2 5 4 2 6 3 4 7 0 4
範例輸出
#2
6
範例輸入
#3
5 5 0 1 5 1 2 6 2 3 2 3 1 4 2 0 3 1 4
範例輸出
#3
-1
測資資訊：
記憶體限制：
256
MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1K
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1M
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1M
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1K
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1M
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1M
提示 ：
標籤: