Submission #1307427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307427		fauntleroy	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	272 ms	19864 KiB

commuter_pass

#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <limits>
#include <tuple>
#include <stack>
#include <bitset>
#include <cstring>
#include <sstream>
#include <functional>
#include <random>
using namespace std;

using ll = long long;

ll inf = 4e18;

vector<vector<pair<int, ll>>> g;

vector<ll> dijkstra(int n, int src) {
    vector<ll> dist(n, inf);
    dist[src] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({ 0,src });
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) {
            continue;
        }
        for (auto& [v, w] : g[u]) {
            ll nd = d + w;
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.emplace(nd, v);
            }
        }
    }
    return dist;
}

void solve() {
    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    s--, t--, u--, v--;
    g.assign(n, {});
    for (int i = 0; i < m; ++i) {
        int a, b;
        ll w;
        cin >> a >> b >> w;
        --a, --b;
        g[a].push_back({ b, w });
        g[b].push_back({ a, w });
    }
    vector<ll> ds = dijkstra(n, s);
    vector<ll> dt = dijkstra(n, t);
    vector<ll> du = dijkstra(n, u);
    vector<ll> dv = dijkstra(n, v);
    
    ll d = ds[t];

    vector<bool> mark(n, 0);
    for (int i = 0; i < n; ++i) {
        if (ds[i] + dt[i] == d) {
            mark[i] = true;
        }
    }

    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int a, int b) { return ds[a] < ds[b]; });

    vector<ll> dp1u(n, inf), dp1v(n, inf);
    for (int i = 0; i < n; ++i) {
        if (mark[i]) {
            dp1u[i] = du[i];
            dp1v[i] = dv[i];
        }
    }

    for (auto& a : ord) {
        if (!mark[a]) {
            continue;
        }
        for (auto& e : g[a]) {
            int b = e.first;
            ll w = e.second;
            if (!mark[b]) {
                continue;
            }
            if (ds[a] + w + dt[b] == d) {
                dp1u[b] = min(dp1u[b], dp1u[a]);
                dp1v[b] = min(dp1v[b], dp1v[a]);
            }
        }
    }

    vector<ll> dp2u(n, inf), dp2v(n, inf);
    for (int i = 0; i < n; ++i) {
        if (mark[i]) {
            dp2u[i] = du[i];
            dp2v[i] = dv[i];
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        int a = ord[i];
        if (!mark[a]) {
            continue;
        }
        for (auto& e : g[a]) {
            int b = e.first;
            ll w = e.second;
            if (!mark[b]) {
                continue;
            }
            if (ds[a] + w + dt[b] == d) {
                dp2u[a] = min(dp2u[a], dp2u[b]);
                dp2v[a] = min(dp2v[a], dp2v[b]);
            }
        }
    }
    ll ans = du[v];
    for (int i = 0; i < n; ++i) {
        if (dp1u[i] < inf && dp2v[i] < inf) {
            ans = min(ans, dp1u[i] + dp2v[i]);
        }
        if (dp1v[i] < inf && dp2u[i] < inf) {
            ans = min(ans, dp1v[i] + dp2u[i]);
        }
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

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