e810. 2.潛水 (Diving)
標籤 :
通過比率 : 160人/189人 ( 85% ) [非即時]
評分方式:
Tolerant

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

內容

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
提示 :
標籤:
出處:
2019年11月TOI練習賽潛力組 [管理者: p3a_owhj (阿普二信) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
41764 toseanlin@gm ... (Dr. SeanXD) e810
C++詳解
75 2024-08-24 22:00
34727 wubaie (小億) e810
346 2023-04-11 11:55