時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
導遊要帶 T 位遊客從城市 S 前往 D。每條雙向道路都有固定的巴士載客上限，導遊自己每趟也占一個名額。可以分多趟運送，沿途可經過其他城市。請選擇路線，使需要的趟數最少。
輸入格式
每筆先有城市數 N（N ≤ 100）與道路數 R。接著 R 行各有 C₁ C₂ P，表示兩城市間巴士容量 P（P > 1）；城市編號為 1 到 N。最後一行為 S D T。以 N = R = 0 結束。
輸出格式
每筆先輸出 Scenario #k，再輸出 Minimum Number of Trips = X，最後另印空白行。k 從 1 起，X 為最少趟數。
範例測資
範例輸入 1
7 10 1 2 30 1 3 15 1 4 10 2 4 25 2 5 60 3 4 40 3 6 20 4 7 35 5 7 20 6 7 30 1 7 99 0 0
範例輸出 1
Scenario #1 Minimum Number of Trips = 5
請先登入後再提交程式碼
討論與題解
載入討論區…