回分類題庫
g053: B.水之國奇幻冒險
關鍵字: NPSC 2009 國中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 136 Times / 91 Users | Submit : 332 Times / 105 Users | Accepted rate : 87%
題目加入時間 : 2011-12-26 14:59

Content: 简体中文

小嘉恩最近在玩一個名叫「水之國奇幻冒險」的小遊戲,其中有一道關卡是這樣的:給挑戰者一張地圖,指定起點和終點,每一條路上有強度不等的水柱攻擊;挑戰者要在起點租借防水車,遊戲的過程中,挑戰者只能經過該防水車能夠抵禦的水柱攻擊的地方。

防水車有各種不同等級的,如果租借等級最高的防水車,挑戰者只要能夠找到一條從起點走到終點的路即可;不過,不同等級的防水車,防水等級越高、租金就越高。小嘉恩覺得這是一個簡單的關卡,不該花費太多水之國幣在這道的關卡上,所以他希望在這關花費的水之國幣越少越好,這樣他才有機會在下一關用比較多的水之國幣換到比較好的裝備。

用下面這張地圖舉例來說,每個點代表不同的路口,每個邊上顯示的數字代表那條路的水柱攻擊強度。如果遊戲指定的起點是A、終點是G,挑戰者可以選擇走ABDG,前提是挑戰者租借的防水車等級必須是 120 以上;如果走ACFDG,挑戰者只需借到等級 80 的防水車即可,同時,這條路需要的防水車等級和租金在這個例子中也是最低的。

小嘉恩希望你可以幫助他找出最省錢的破關方法。小嘉恩原本打算請你告訴他哪條路需要的防水車等級最低,後來他覺得這樣就沒有玩遊戲的樂趣了,所以你只要告訴他應該租借防水等級多少的防水車即可。

Input:

第一行有一個整數 T,代表總共有 T 筆測試資料。
每一筆測試資料的第一行有二個整數 N 和 M (2<=N<=100),1<=M<=N×(N-1)/2),分別代表 N 個街口和 M 條街。
接下來有 M 行資料,用來描述每一條街。每一行有三個整數 a, b 和 p (1<=a、b<=N,a!=b,1<=p<=200),a 和 b 是一條街的兩個端點,p 代表該條街上水柱攻擊的強度。每條街都是雙向道,而且固定兩個端點 a 和 b 時,同時以 a 和 b 為街口的街最多只會有一條。

Output:

每一筆測試資料輸出一行,每一行包括一個整數,代表要租借防水等級為多少的防水車,才可以從街口 1 安全抵達街口 N,同時又能達到最省錢的目標。因為這個遊戲被設定成一定可以破關,所以不必擔心沒有路徑可以到達的情況。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
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

Sample Output :

80
40

Hint :

Author :

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

  Solve it!   Status Forum