時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
卡車本身的載重沒有實際限制，但每條道路都有載重上限。給定起點與終點城市，請找出存在可通行路徑時能運送的最大貨物重量。某條路徑的可載重量受其中最小的道路限重限制。
輸入格式
每筆資料先有城市數 n 與道路數 r，2 ≤ n ≤ 200，1 ≤ r ≤ 19900。接著 r 行各有兩個城市名稱與道路限重；道路雙向通行，限重為 0 到 10000 的整數，城市名稱不含空白且最多 30 字元。最後一行是起點與終點名稱。以 n = r = 0 結束。
輸出格式
每筆輸出三行：Scenario #x、y tons、空白行。x 從 1 起，y 為最大可運送重量。
範例測資
範例輸入 1
4 3 Karlsruhe Stuttgart 100 Stuttgart Ulm 80 Ulm Muenchen 120 Karlsruhe Muenchen 5 5 Karlsruhe Stuttgart 100 Stuttgart Ulm 80 Ulm Muenchen 120 Karlsruhe Hamburg 220 Hamburg Muenchen 170 Muenchen Karlsruhe 0 0
範例輸出 1
Scenario #1 80 tons Scenario #2 170 tons
請先登入後再提交程式碼
討論與題解
載入討論區…