Submission #1273380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273380		ericl23302	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	271 ms	23828 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1e18;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    --s;
    --t;
    --u;
    --v;
    vector<vector<pair<int, ll>>> adjacency(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        --a;
        --b;
        adjacency[a].emplace_back(b, c);
        adjacency[b].emplace_back(a, c);
    }

    auto dijkstra1 = [&](int start, vector<ll> &dist) {
        dist.assign(n, INF);
        priority_queue<pair<ll, int>> pq;
        pq.emplace(0, start);
        dist[start] = 0;
        while (!pq.empty()) {
            auto [curDist, cur] = pq.top();
            pq.pop();
            curDist = -curDist;
            if (curDist != dist[cur]) continue;
            for (auto &[adj, len] : adjacency[cur]) {
                if (dist[adj] > curDist + len) {
                    dist[adj] = curDist + len;
                    pq.emplace(-curDist - len, adj);
                }
            }
        }
    };

    vector<ll> distU(n), distV(n);
    dijkstra1(u, distU);
    dijkstra1(v, distV);
    ll ans = distU[v];

    auto dijkstra2 = [&](int start, int end) {
        vector<ll> dp0(n, INF), dp1(n, INF), dist(n, INF);
        vector<bool> visited(n, false);
        priority_queue<pair<ll, pair<int, int>>> pq;
        dist[start] = 0;
        pq.push({0, {start, 0}});
        while (!pq.empty()) {
            auto [curDist, curPar] = pq.top();
            pq.pop();
            if (!visited[curPar.first]) {
                visited[curPar.first] = true;
                dist[curPar.first] = -curDist;
                dp0[curPar.first] =
                    min(distU[curPar.first], dp0[curPar.second]);
                dp1[curPar.first] =
                    min(distV[curPar.first], dp1[curPar.second]);
                for (auto &[adj, len] : adjacency[curPar.first])
                    pq.push({curDist - len, {adj, curPar.first}});
            } else if (-curDist == dist[curPar.first]) {
                if (min(distU[curPar.first], dp0[curPar.second]) +
                        min(distV[curPar.first], dp1[curPar.second]) <
                    dp0[curPar.first] + dp1[curPar.first]) {
                    dp0[curPar.first] =
                        min(distU[curPar.first], dp0[curPar.second]);
                    dp1[curPar.first] =
                        min(distV[curPar.first], dp1[curPar.second]);
                }
            }
        }

        ans = min(ans, dp0[end] + dp1[end]);
    };

    dijkstra2(s, t);
    dijkstra2(t, s);

    cout << ans << '\n';

    return 0;
}

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