Submission #1273191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273191		vk3601h	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	231 ms	20284 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    s--; t--; u--; v--;

    vector<vector<pair<int, long long>>> adj(n);
    for (int i = 0; i < m; i++){
        int a, b;
        long long c;
        cin >> a >> b >> c;
        a--; b--;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }

    auto dijkstra1 = [&](int start) -> vector<long long> {
        vector<long long> dist(n, INF);
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
        dist[start] = 0;
        pq.push({0, start});
        while (!pq.empty()) {
            long long d = pq.top().first;
            int curr = pq.top().second;
            pq.pop();
            if (d != dist[curr]) continue;
            for (auto [next, cost] : adj[curr]) {
                if (dist[next] > d + cost) {
                    dist[next] = d + cost;
                    pq.push({dist[next], next});
                }
            }
        }
        return dist;
    };

    vector<long long> du = dijkstra1(u);
    vector<long long> dv = dijkstra1(v);

    auto dijkstra2 = [&](int start, int end) -> long long {
        vector<long long> dist(n, INF);
        vector<long long> dp0(n, INF), dp1(n, INF);
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

        dist[start] = 0;
        dp0[start] = du[start];
        dp1[start] = dv[start];
        pq.push({0, start});

        while (!pq.empty()) {
            long long d = pq.top().first;
            int curr = pq.top().second;
            pq.pop();

            if (d > dist[curr]) continue;

            for (auto [next, cost] : adj[curr]) {
                long long new_d = d + cost;
                if (new_d < dist[next]) {
                    dist[next] = new_d;
                    dp0[next] = min(du[next], dp0[curr]);
                    dp1[next] = min(dv[next], dp1[curr]);
                    pq.push({new_d, next});
                } else if (new_d == dist[next]) {
                    long long cand0 = min(du[next], dp0[curr]);
                    long long cand1 = min(dv[next], dp1[curr]);
                    if (cand0 + cand1 < dp0[next] + dp1[next]) {
                        dp0[next] = cand0;
                        dp1[next] = cand1;
                        pq.push({new_d, next});
                    }
                }
            }
        }

        return dp0[end] + dp1[end];
    };

    long long ans = du[v];
    ans = min(ans, dijkstra2(s, t));
    ans = min(ans, dijkstra2(t, s));
    cout << ans << endl;

    return 0;
}

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