Submission #1283761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283761		yanb	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	328 ms	23080 KiB

commuter_pass

#include <bits/stdc++.h>

#define int long long

using namespace std;

using pii = pair<int, int>;
using t3i = tuple<int, int, int>;

int n, m, S, T, U, V;
vector<vector<pii>> g;

vector<int> dst(int v) {
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, v});
    vector<int> d(n, 1e17);

    while (!q.empty()) {
        auto [dv, v] = q.top();
        q.pop();
        if (d[v] <= dv) continue;
        d[v] = dv;

        for (auto [u, c] : g[v]) {
            q.push({dv + c, u});
        }
    }

    return d;
}

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

    cin >> n >> m >> S >> T >> U >> V;
    S--; T--; U--; V--;

    g.resize(n);
    for (int i = 0; i < m; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        x--; y--;
        g[x].push_back({y, c});
        g[y].push_back({x, c});
    }

    vector<int> dS = dst(S), dT = dst(T), dU = dst(U), dV = dst(V);
    
    vector<pii> dSi(n);
    for (int i = 0; i < n; i++) dSi[i] = {dS[i], i};
    sort(dSi.begin(), dSi.end());

    vector<int> dpU(n, 1e17), dpV(n, 1e17);
    int ans = dU[V];

    for (auto [_, v] : dSi) {
        dpU[v] = min(dpU[v], dU[v]);
        dpV[v] = min(dpV[v], dV[v]);
        for (auto [u, c] : g[v]) {
            if (dS[u] + c == dS[v] && dT[u] == dT[v] + c) {
                dpU[v] = min(dpU[v], dpU[u]);
                dpV[v] = min(dpV[v], dpV[u]);
            }
        }
        ans = min({ans, dpU[v] + dV[v], dpV[v] + dU[v]});
    }

    cout << ans << "\n";
}

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