ZeroJudge E810: Diving

Xiao Xuan is a diving enthusiast who is taking advantage of his summer vacation to go diving in Penghu. Penghu consists of many small islands, and today, Xiao Xuan wants to dive from Island A to Island B. Diving requires carrying an oxygen tank, and Xiao Xuan doesn't want to waste energy carrying an overly heavy tank; he wants the tank's capacity to be just enough. The distances between the islands vary, as does the amount of oxygen needed to travel between them, and some islands cannot be reached by diving. At each island, the oxygen tank can be refilled. Please help Xiao Xuan calculate the minimum capacity of the oxygen tank he needs to successfully dive from Island A to Island B.

Sample Inputs/Outputs

Thought Process

Declare a Map<int, vector<pair>> to store the data, where the second in the pair is used to store W. Declare a variable ans with a default value of 999999, and an array point[1000] where elements from 0 to N-1 are also set to 999999 by default, but the point at index A should be set to 0.

Run BFS, and each time determine the next points from the current point. If point[current_position] > ans, then skip this point and continue. Also, declare a Map named all_walk outside of the function to record which points have been visited. Each time you enter the loop, increment all_walk[current_position]++.

In BFS, for each point you reach, there will be subsequent points you can move to. Declare a variable newValue = max(point[current_BFS_position], W_of_next_point). If all_walk records that this next point has not been visited, or if newValue < point[next_point], then increment all_walk[next_point]++, update point[next_point] to newValue, and push the next point into the BFS queue for the next iteration.

If during the process you reach the endpoint B, set ans = min(ans, point[current_position]). Additionally, declare a global boolean variable to confirm whether you have reached the endpoint.

Sample Code－ZeroJudge E810: Diving

#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