d589. B. 水之國的奇幻冒險
http://zerojudge.tw/ShowProblem?problemid=d589
內容 ：
小嘉恩最近在玩一個名叫「水之國奇幻冒險」的小遊戲，其中有一道關卡是這樣的：給挑戰者一張地圖，指定起點和終點，每一條路上有強度不等的水柱攻擊；挑戰者要在起點租借防水車，遊戲的過程中，挑戰者只能經過該防水車能夠抵禦的水柱攻擊的地方。
防
水車有各種不同等級的，如果租借等級最高的防水車，挑戰者只要能夠找到一條從起點走到終點的路即可；不過，不同等級的防水車，防水等級越高、租金就越高。
小嘉恩覺得這是一個簡單的關卡，不該花費太多水之國幣在這道的關卡上，所以他希望在這關花費的水之國幣越少越好，這樣他才有機會在下一關用比較多的水之國
幣換到比較好的裝備。
用下面這張地圖舉例來說，每個點代表不同的路口，每個邊上顯示的數字代表那條路的水柱攻擊強度。如果遊戲指定的起點是
A、終點是 G，挑戰者可以選擇走 ABDG，前提是挑戰者租借的防水車等級必須是 120 以上；如果走 ACFDG，挑戰者只需借到等級 80
的防水車即可，同時，這條路需要的防水車等級和租金在這個例子中也是最低的。
小嘉恩希望你可以幫助他找出最省錢的破關方法。小嘉恩原本打算請你告訴他哪條路需要的防水車等級最低，後來他覺得這樣就沒有玩遊戲的樂趣了，所以你只要告訴他應該租借防水等級多少的防水車即可。
輸入說明
：
第一行有一個整數 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 為街口的街最多只會有一條。
輸出說明
：
每一筆測試資料輸出一行，每一行包括一個整數，代表要租借防水等級為多少的防水車，才可以從街口 1 安全抵達街口 N，同時又能達到最省錢的目標。
因為這個遊戲被設定成一定可以破關，所以不必擔心沒有路徑可以到達的情況。
範例輸入 ：
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
提示
：
出處
：
/**********************************************************************************/
/* Problem: d589 "B. 水之國的奇幻冒險" from 2009 NPSC 國中組初賽 */
/* Language: C */
/* Result: AC (36ms, 340KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-12 17:00:12 */
/**********************************************************************************/
#include<stdio.h>
#define Max 201
struct link {
int t, node[101], w[101];
}Map[101];
void SPFA (int N) {
int a, b, c;
int Queue[10001], Qt = 0, tn, tw;
int Used[101] = {}, V[101] = {};
for(a = 1; a<= N; a++) V[a] = Max;
Queue[0] = 1, Used[1] = 1, V[1] = 0;
for(a = 0; a <= Qt; a++) {
tn = Queue[a];
for(b = 0; b < Map[tn].t; b++) {
tw = (V[tn] > Map[tn].w[b]) ? V[tn] : Map[tn].w[b];
if(tw < V[Map[tn].node[b]]) {
V[Map[tn].node[b]] = tw;
if(Used[Map[tn].node[b]] == 0)
Queue[++Qt] = Map[tn].node[b], Used[Map[tn].node[b]] = 1;
}
}
Used[tn] = 0;
}
printf("%d\n", V[N]);
}
main() {
int T, x, y, w, N, M, a;
scanf("%d", &T);
while(T--) {
scanf("%d %d", &N, &M);
for(a = 1; a <= N; a++) Map[a].t = 0;
for(a = 0; a < M; a++) {
scanf("%d %d %d", &x, &y, &w);
Map[x].node[Map[x].t] = y, Map[x].w[Map[x].t] = w;
Map[y].node[Map[y].t] = x, Map[y].w[Map[y].t] = w;
Map[x].t++, Map[y].t++;
}
SPFA(N);
}
return 0;
}
上一篇：b255. D. 跑跑卡丁車
下一篇：d932. D. 流水不腐