ZeroJudge E810: 潛水

小軒是一個熱愛潛水的人，他趁著放暑假的時間去澎湖潛水。澎湖由許多小島組成，小軒今天想從 A 島經由潛水的方式到 B 島。潛水需要背著氧氣筒，而 小軒不想浪費力氣去背過重的氧氣筒，他希望氧氣筒的容量夠用就好。小島間的距離有長有短，需要花費的氧氣量也不同，但有些島之間不能由潛水來移動；每抵達一座島就可以把氧氣筒重新裝滿。請你幫小軒算出他最少要背多少容量的氧氣筒才能讓他順利從 A 島潛水抵達 B 島。

範例測資

範例輸入範例輸出
第一列有兩個整數 N 與 M（2 <= N <= 500、0 <= M <= N*(N-1)/2），代表有 N 座小 島以及 M 條潛水路徑，小島的編號為 0～N-1。接下去有 M 列，代表島與島之間移動所需花費的氧氣量；每列有三個整數，前兩個整數為島的編號，第三個整數為兩個島之間潛水移動需要的氧氣量 W (2 <= W <= 50000)，雙向所需要的氧氣量相等。最後一列有兩個整數 A 與 B，代表小軒想從 A 島潛水移動到 B 島。請輸出小軒最少要背多少容量的氧氣筒，若從 A 島無法經由潛水移動到 B 島，請輸出 -1。
4 4
0 2 3
0 1 1
1 3 6
2 3 5
0 3		5
5 6
0 1 1
0 2 2
1 3 4
3 2 5
4 2 6
3 4 7
0 4		6
5 5
0 1 5
1 2 6
2 3 2
3 1 4
2 0 3
1 4		-1
ZeroJudge E810 範例測資

解題思路

宣告一個 Map<int, vector<pair<int, int>>> 來存資料，pair 中的 second 是用來存 W 用的。宣告一個 ans 變數預設為 999999，還有一個陣列 point[1000] 裡面從 0 到 N-1 預設也是 999999，但是要將第 A 個位置的 point 設為 0。

跑 BFS，每一次就是判斷起點中的點的下一些點有誰，如果 point[目前判斷的位置] > ans，則不用判斷這個點直接 continue。並且要在函式外面宣告一個 all_walk 的 Map 來紀錄哪些點有走過了，每一次進到迴圈都要將 all_walk[目前位置]++。

在 BFS 中跑到的點都會有其下一個可以走到的點，宣告一個 newValue 變數 = max(point[目前 BFS 位置], 下一個點的 W)。如果 all_walk 中紀錄這個點沒有被走過，或是 newValue < point[下一個點]，就將 all_walk[下一個點]++、將 point[下一個點] 更新成 newValue、並且將下一個點 Push_Back 到下一次的 BFS 起點中。

如果過程中跑到了 B 這個終點，則將 ans = min(ans, point[目前位置])，並且要宣告一個全域布林值來確認是否真的有走到終點過。

範例程式碼－ZeroJudge E810: 潛水

#include <iostream>
#include <vector>
#include <map>
using namespace std;

pair<int, int> p (const int a, const int b) {
    pair<int, int>tmp;
    tmp.first = a;
    tmp.second = b;
    return tmp;
}

int A, B, ans = 99999999, point[1000] = {};
map<int, vector<pair<int, int>>>road;
map<int, int>all_walk;
bool ok = false;

void BFS(const vector<int>start) {
    if (start.size() == 0) return;
    vector<int>newStart;
    for (int i = 0; i<start.size(); i++) {
        const int position = start[i];
        const int oxygen = point[position];
        if (oxygen > ans) continue;
        if (position == B) {
            ok = true;
            ans = min(ans, oxygen);
        }
        all_walk[position]++;
        const vector<pair<int, int>> begin = road[position];
        for (int j = 0; j<begin.size(); j++) {
            const int current = begin[j].first;
            const int newValue = max(begin[j].second, oxygen);
            if (all_walk[current] == 0 || newValue < point[current]) {
                all_walk[current]++;
                point[current] = newValue;
                newStart.push_back(current);
            }
        }
    }
    BFS(newStart);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    for (int i = 0; i<N; i++) point[i] = 99999999;
    for (int i = 0; i<M; i++) {
        int a, b, W;
        cin >> a >> b >> W;
        road[a].push_back(p(b, W));
        road[b].push_back(p(a, W));
    }
    cin >> A >> B;
    vector<int>start;
    start.push_back(A);
    point[A] = 0;
    BFS(start);
    if (ok) cout << ans << "\n";
    else cout << "-1\n";
}

//ZeroJudge E810
//Dr. SeanXD
標籤

相關文章

發佈留言