Submission #849470

#	Time	Username	Problem	Language	Result	Execution time	Memory
849470		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	254 ms	24116 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

int32_t 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, int>>> adj(N);
        for (int i = 0; i < M; i++) {
                int u, v, w;
                cin >> u >> v >> w;
                u--, v--;
                adj[u].emplace_back(v, w);
                adj[v].emplace_back(u, w);
        }

        auto dijkstra = [&](vector<int64_t>& d, int source) {
                fill(d.begin(), d.end(), 1e18);
                d[source] = 0;
                priority_queue<pair<int64_t, int>> pq;
                pq.emplace(0, source);
                while (pq.size()) {
                        auto [du, u] = pq.top();
                        pq.pop();
                        if (d[u] != -du) continue;
                        for (auto [v, w] : adj[u]) {
                                if (d[v] > -du + w) {
                                        d[v] = -du + w;
                                        pq.emplace(-d[v], v);
                                }
                        }
                }
        };

        vector<int64_t> dS(N), dT(N), dU(N), dV(N);
        dijkstra(dS, S);
        dijkstra(dT, T);
        dijkstra(dU, U);
        dijkstra(dV, V);

        int64_t min_dist = dS[T];

        auto calc = [&](const vector<int64_t>& ds, const vector<int64_t>& dt, const vector<int64_t>& du, vector<int64_t>& best, int s) {
                fill(best.begin(), best.end(), 1e18);
                vector<int> topo;
                vector<int> vis(N, 0);
                function<void(int)> toposort = [&](int u) {
                        vis[u] = 1;
                        for (auto [v, w] : adj[u]) {
                                if (ds[u] + w == min_dist - dt[v] && vis[v] == 0) {
                                        toposort(v);
                                }
                        }
                        topo.emplace_back(u);
                };
                toposort(s);
                reverse(topo.begin(), topo.end());
                for (int i : topo) {
                        best[i] = min(best[i], du[i]);
                        for (auto [j, w] : adj[i]) {
                                if (ds[i] + w == min_dist - dt[j]) {
                                        best[j] = min(best[j], best[i]);
                                }
                        }
                }
        };

        vector<int64_t> dSU(N), dSV(N), dTU(N), dTV(N);
        calc(dS, dT, dU, dSU, S);
        calc(dS, dT, dV, dSV, S);
        calc(dT, dS, dU, dTU, T);
        calc(dT, dS, dV, dTV, T);

        int64_t res = 2e18;
        for (int i = 0; i < N; i++) {
                res = min(res, min(dSU[i] + dTV[i], dSV[i] + dTU[i]));
        }

        cout << min(res, dU[V]);
}

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