e810: 2.潛水 (Diving)
Tags :
Accepted rate : 18人/23人 ( 78% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-01-04 21:39

Content

TOI練習賽_2019/11_a2.潛力組2.潛水 (Diving) {試題連結}

問題敘述

小軒是一個熱愛潛水的人,他趁著放暑假的時間去澎湖潛水。澎湖由許多小 島組成,小軒今天想從 A 島經由潛水的方式到 B 島。潛水需要背著氧氣筒,而 小軒不想浪費力氣去背過重的氧氣筒,他希望氧氣筒的容量夠用就好。小島間的 距離有長有短,需要花費的氧氣量也不同,但有些島之間不能由潛水來移動;每 抵達一座島就可以把氧氣筒重新裝滿。請你幫小軒算出他最少要背多少容量的氧 氣筒才能讓他順利從 A 島潛水抵達 B 島。

 

 

Input

第一列有兩個整數 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 島。

Output

請輸出小軒最少要背多少容量的氧氣筒,若從 A 島無法經由潛水移動到 B 島,請輸出 -1。

Sample Input #1
4 4
0 2 3
0 1 1
1 3 6
2 3 5
0 3
Sample Output #1
5
Sample Input #2
5 6
0 1 1
0 2 2
1 3 4
3 2 5
4 2 6
3 4 7
0 4
Sample Output #2
6
Sample Input #3
5 5
0 1 5
1 2 6
2 3 2
3 1 4
2 0 3
1 4
Sample Output #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
Hint :
Tags:
出處:
2019年11月TOI練習賽潛力組 [管理者:
p3a_owhj (阿普二信)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」