Submission #922113

#	Time	Username	Problem	Language	Result	Execution time	Memory
922113		406	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	294 ms	29344 KiB

commuter_pass

#include <bits/stdc++.h>
#define int int64_t
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;
using ar = array<int, 2>;

const int64_t INF = 1ll << 60;
const int N = 2e5 + 5;

int n, m, S, T, U, V, d[4][N], mnd, X[N], tmp[2][N];
vector<ar> adj[N];

void dij(int x, int d[]) {
        fill(d, d + N, INF);
        priority_queue<ar> q;
        q.push({d[x] = 0, x});
        while (q.size()) {
                auto [di, v] = q.top();
                q.pop();
                if (-di > d[v]) continue;
                for (auto [u, w]: adj[v]) {
                        w += d[v];
                        if (w < d[u]) {
                                d[u] = w;
                                q.push({-d[u], u});
                        }
                }
        }
}

signed main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr); 
        cin >> n >> m >> S >> T >> U >> V;
        --S, --T, --U, --V;
        FOR(i, 0, m) {
                int u, v, w;
                cin >> u >> v >> w;
                --u, --v;
                adj[v].push_back({u, w});
                adj[u].push_back({v, w});
        }
        dij(T, d[0]);
        dij(S, d[1]);
        dij(U, d[2]);
        dij(V, d[3]);

        FOR(v, 0, n) for (auto &[u, w]: adj[v]) 
                w = w + d[0][v] + d[1][u] == d[0][S] ? 0 : w;
        iota(X, X + n, 0);
        sort(X, X + n, [&](const int u, const int v) {return d[0][u] < d[0][v];});
        for (int i = n - 1; i >= 0; --i) {
                int v = X[i];
                tmp[0][v] = d[2][v];
                tmp[1][v] = d[3][v];
                for (auto [u, w]: adj[v]) if (!w) {
                        FOR(i, 0, 2) 
                                tmp[i][v] = min(tmp[i][v], tmp[i][u]);
                }
        }
        int mn = INF;
        FOR(v, 0, n) mn = min({d[3][v] + tmp[0][v], d[2][v] + tmp[1][v], mn});
        cout << mn << '\n';
        return 0;
}

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