Submission #921811

#	Time	Username	Problem	Language	Result	Execution time	Memory
921811		garamlee500	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	237 ms	28044 KiB

commuter_pass

#include <iostream>
#include <queue>
#include <limits>
using namespace std;



vector<pair<int, long long>> edges[100001];
long long u_distances[100001];
long long best_entry[100001];
long long best_finished[100001];
long long rbest_entry[100001];
long long rbest_finished[100001];

long long v_distances[100001];
long long s_distances[100001];
int n, m, s, t, u, v, a, b;
long long c;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> s >> t >> u >> v;
    while (m--){
        cin >> a >> b >> c;
        edges[a].emplace_back(b, c);
        edges[b].emplace_back(a, c);
    }


    for (int i = 1; i <= n; i++){
        u_distances[i] = numeric_limits<long long>::max();
    }
    u_distances[u] = 0;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> q1;
    q1.emplace(0, u);
    while (!q1.empty()){
        long long d1 = q1.top().first;
        long long node = q1.top().second;
        q1.pop();
        if (u_distances[node]!=d1){
            continue;
        }
        for (auto [connected, length] : edges[node]){
            if (d1 + length < u_distances[connected]){
                u_distances[connected] = d1+length;
                q1.emplace(d1+length, connected);
            }
        }
    }

    for (int i = 1; i <= n; i++){
        v_distances[i] = numeric_limits<long long>::max();
    }
    v_distances[v] = 0;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> q2;
    q2.emplace(0, v);
    while (!q2.empty()){
        long long d1 = q2.top().first;
        long long node = q2.top().second;
        q2.pop();
        if (v_distances[node]!=d1){
            continue;
        }
        for (auto [connected, length] : edges[node]){
            if (d1 + length < v_distances[connected]){
                v_distances[connected] = d1+length;
                q2.emplace(d1+length, connected);
            }
        }
    }

    for (int i = 1; i <= n; i++){
        s_distances[i] = numeric_limits<long long>::max();
        best_entry[i] = numeric_limits<long long>::max();
        best_finished[i] = numeric_limits<long long>::max();

        rbest_entry[i] = numeric_limits<long long>::max();
        rbest_finished[i] = numeric_limits<long long>::max();
    }

    s_distances[s] = 0;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> q3;
    q3.emplace(0, s);
    while (!q3.empty()){
        long long d1 = q3.top().first;
        long long node = q3.top().second;
        q3.pop();
        if (s_distances[node]!=d1){
            continue;
        }

        best_entry[node] = min(best_entry[node], u_distances[node]);
        best_finished[node] = min(best_finished[node], v_distances[node] + best_entry[node]);
        rbest_entry[node] = min(rbest_entry[node], v_distances[node]);
        rbest_finished[node] = min(rbest_finished[node], u_distances[node] + rbest_entry[node]);

        for (auto [connected, length] : edges[node]){
            if (d1 + length < s_distances[connected]){
                s_distances[connected] = d1 + length;
                q3.emplace(d1+length, connected);
                best_entry[connected] = best_entry[node];
                best_finished[connected] = best_finished[node];

                rbest_entry[connected] = rbest_entry[node];
                rbest_finished[connected] = rbest_finished[node];
            }
            else if (d1 + length == s_distances[connected]){
                best_entry[connected] = min(best_entry[node], best_entry[connected]);
                best_finished[connected] = min(best_finished[node], best_finished[connected]);

                rbest_entry[connected] = min(rbest_entry[node], rbest_entry[connected]);
                rbest_finished[connected] = min(rbest_finished[node], rbest_finished[connected]);

            }

        }
    }
    cout << min(min(best_finished[t], rbest_finished[t]), u_distances[v]);

}

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45