小嘉恩最近在玩一個名叫「水之國奇幻冒險」的小遊戲，其中有一道關卡是這樣的：給挑戰者一張地圖，指定起點和終點，每一條路上有強度不等的水柱攻擊；挑戰者要在起點租借防水車，遊戲的過程中，挑戰者只能經過該防水車能夠抵禦的水柱攻擊的地方。
防水車有各種不同等級的，如果租借等級最高的防水車，挑戰者只要能夠找到一條從起點走到終點的路即可；不過，不同等級的防水車，防水等級越高、租金就越高。小嘉恩覺得這是一個簡單的關卡，不該花費太多水之國幣在這道的關卡上，所以他希望在這關花費的水之國幣越少越好，這樣他才有機會在下一關用比較多的水之國幣換到比較好的裝備。
用下 這張地圖舉例來說，每個點代表不同的路口，每個邊上顯示的數字代表那條路的水柱攻擊強度。如果遊戲指定的起點是 A、終點是 G，挑戰者可以選擇走 ABDG，前提是挑戰者租借的防水車等級必須是以上；如果走 ACFDG，挑戰者只需借到等級的防水車即可，同時，這條路需要的防水車等級和租金在這個例子中也是最低的。
小嘉恩希望你可以幫助他找出最省錢的破關方法。小嘉恩原本打算請你告訴他哪條路需要的防水車等級最低，後來他覺得這樣就沒有玩遊戲的樂趣了，所以你只要告訴他應該租借防水等級多少的防水車即可。
第一行有一個整數，代表總共有筆測試資料。每一筆測試資料的第一行有二個整數 和 ，
，分別代表個街口和條街。
接下來有行資料，用來描述每一條街。每一行有三個整數 和
， 和 是一條街的兩個端點，代表該條街上水柱攻擊的強度。每條街都是雙向道，而且固定兩個端點 和時，同時以 和 為街口的街最多只會有一條。
每一筆測試資料輸出一行，每一行包括一個整數，代表要租借防水等級為多少的防水車，才可以從街口安全抵達街口，同時又能達到最省錢的目標。因為這個遊戲被設定成一定可以破關，所以不必擔心沒有路徑可以到達的情況。
2 7 9 1 2 50 1 3 60 2 4 120 2 5 90 3 6 50 4 6 80 4 7 70 5 7 40 6 7 140 7 6 1 7 40 2 4 120 2 5 50 3 5 60 3 6 50 4 6 80
80 40
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||