d589. B. 水之國的奇幻冒險＠Morris' Blog

2011-06-14 22:12:56| 人氣1,097| 回應0 | 上一篇 | 下一篇

d589. B. 水之國的奇幻冒險

推薦 0 收藏 0 轉貼0 訂閱站台

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，同時又能達到最省錢的目標。

因為這個遊戲被設定成一定可以破關，所以不必擔心沒有路徑可以到達的情況。

範例輸入：

範例輸出：

80
40

提示：

出處：

2009 NPSC 國中組初賽 (管理：example)

作法 : SPFA
逐步更新最佳解

/**********************************************************************************/
/* 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;
}

我要檢舉

#d589#B. 水之國的奇幻冒險

台長： Morris

您可能對以下文章有興趣

b255. D. 跑跑卡丁車

[NPSC][方格法] b256. E. 大風吹

[ZJ][KM算法] d210. 老問題

[ZJ][翻轉處理] a315. D 滿州國皇帝之璽

人氣(1,097) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: NPSC |
此分類下一篇:d932. D. 流水不腐
此分類上一篇:b255. D. 跑跑卡丁車

回應(0)