Submission #1143532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143532		poltanos	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	380 ms	27304 KiB

commuter_pass

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

const int inf = 1e18;

vector<vector<pair<int, int>>> graph(1e5 + 1);
vector<int> du(1e5 + 1, inf), dv(1e5 + 1, inf), ds(1e5 + 1, inf);
vector<vector<int>> dp(2, vector<int>(1e5 + 1));
vector<bool> vis(1e5 + 1);
int ans;

void dijkstra1(int start, vector<int> &arr) {
    // Reset the visited vector for this run.
    fill(vis.begin(), vis.end(), false);
    arr[start] = 0;

    priority_queue<pair<int, int>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [c, node] = pq.top();
        pq.pop();

        if (vis[node]) continue;
        vis[node] = true;

        for (auto [b, wt] : graph[node]) {
            if (arr[node] + wt < arr[b]) {
                arr[b] = arr[node] + wt;
                pq.push({-arr[b], b});
            }
        }
    }
}

void dijkstra2(int start, int end) {
    // Reset dp arrays with "inf" for this run.
    fill(dp[0].begin(), dp[0].end(), inf);
    fill(dp[1].begin(), dp[1].end(), inf);
    // Reset the visited vector.
    fill(vis.begin(), vis.end(), false);

    priority_queue<pair<int, pair<int, int>>> pq;
    pq.push({0, {start, 0}});
    // Set the dp value for the dummy parent (index 0) to inf.
    dp[0][0] = dp[1][0] = inf;

    while (!pq.empty()) {
        auto [c, p] = pq.top();
        auto [node, par] = p;
        pq.pop();

        if (!vis[node]) {
            vis[node] = true;
            ds[node] = -c;
            // Propagate the best hook-in costs.
            dp[0][node] = min(du[node], dp[0][par]);
            dp[1][node] = min(dv[node], dp[1][par]);

            for (auto &edge : graph[node]) {
                int next = edge.first, w = edge.second;
                pq.push({c - w, {next, node}});
            }
        } else if (-c == ds[node]) {
            // If we reach node with the same corridor distance,
            // update dp values if the candidate parent's values are better.
            if (min(du[node], dp[0][par]) + min(dv[node], dp[1][par]) <= dp[0][node] + dp[1][node]) {
                dp[0][node] = min(du[node], dp[0][par]);
                dp[1][node] = min(dv[node], dp[1][par]);
            }
        }
    }

    ans = min(ans, dp[0][end] + dp[1][end]);
}

void solve() {
    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }

    dijkstra1(u, du);
    dijkstra1(v, dv);

    ans = du[v];

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

    cout << ans << endl;
}

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

    int t = 1;
    while (t--) solve();

    return 0;
}

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