回分類題庫
g017: D.水之都
關鍵字: NPSC 2006 國中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 85 Times / 58 Users | Submit : 216 Times / 66 Users | Accepted rate : 88%
題目加入時間 : 2011-12-13 09:32

Content: 简体中文

威尼斯──位於義大利東北部,素有「水都」的美稱,市內道路狹窄,運河交錯。步行外,水上交通是主要的代步方法。

一般人對於威尼斯的印象,總是浪漫、美麗的,但實際上縱橫交錯的大小運河給當地居民帶來許多不便。交通不便、水道污染等等,其實和想像中美麗的水鄉澤國有些差距。

在交通上面,由於無法使用汽車,一般代步、運輸都需要透過代步小船。儘管人們希望小船的載重能力越大越好,但因水道的寬度限制,每條水道能通過的小船的尺寸是被限制的,同時也限制了小船的載重能力。

有商人在這個城市中提供貨運的服務:將顧客所交付的貨物從顧客所在地點運至指定的目的地,但因為上述原因,運送的物品是有重量限制的。假設不考慮運送時間,商人自然希望一個船隻能夠運送的重量越大越好。現在你的任務就是替商人計算出兩地之間單一船隻能運送的最大重量。

Input:

輸入檔中有多筆測試資料。每筆測試資料第一行有兩個正整數 N, M(1 ≦ N ≦ 1000),分別代表地圖上水道交叉點(編號從 1 到 N)的數目,以及水道的數目。接下來 M 行每行代表一條水道的資料,以三個數字 Xa, Xb, C 代表水道的兩端交叉點的編號以及能通過此水道的船之最大載重量。水道為雙向的,可從兩個方向運輸。最後一行有兩個數字S, D,分別代表顧客所在地以及目的地的編號。遇到第一行為兩個零“0 0”為檔案結束,不須處理這組輸入。

Output:

對於每筆測資,輸出此筆資料中所能運送的最大重量,如果無法運送則輸出0。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
4 4
1 2 10
1 3 12
2 4 15
3 4 11
1 4
0 0

Sample Output :

11

Hint :

請注意,兩點之間可以有不只一條的水道。

Author :

NPSC 2006 國中組初賽 (管理員:sagit)

  Solve it!   Status Forum