Submission #989340

#	Time	Username	Problem	Language	Result	Execution time	Memory
989340		eysbutno	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	185 ms	23740 KiB

commuter_pass

#pragma GCC optimize("O3")

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = array<int, 2>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

template<class T> bool smax(T &a, T b) {
    return a < b ? a = b, 1 : 0;
}
template<class T> bool smin(T &a, T b) {
    return a > b ? a = b, 1 : 0;
}
constexpr ll INF = 1e18;
int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    pii a, b;
    cin >> a[0] >> a[1] >> b[0] >> b[1];
    --a[0], --a[1], --b[0], --b[1];
    vector<vector<pii>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[--u].push_back({--v, w});
        adj[v].push_back({u, w});
    }
    using pll = array<ll, 2>;
    vector<vector<int>> alt(n);
    priority_queue<pll, vector<pll>, greater<>> pq;
    {
        vector<ll> tdist(n, INF);
        pq.push({tdist[a[0]] = 0, a[0]});
        while (!pq.empty()) {
            auto [t, u] = pq.top(); pq.pop();
            if (tdist[u] != t) continue;
            for (auto [v, w] : adj[u]) {
                if (smin(tdist[v], t + w)) {
                    alt[v] = {(int) u};
                    pq.push({tdist[v], v});
                } else if (tdist[v] == t + w) {
                    alt[v].push_back((int) u);
                }
            }
        }
    }
    vector dist(2, vector(n, INF));
    for (int id = 0; id < 2; id++) {
        pq.push({dist[id][b[id]] = 0, b[id]});
        while (!pq.empty()) {
            auto [t, u] = pq.top(); pq.pop();
            if (t != dist[id][u]) continue;
            for (auto [v, w] : adj[u]) {
                if (smin(dist[id][v], t + w)) {
                    pq.push({t + w, v});
                }
            }
        }
    }
    ll res = dist[0][b[1]];
    vector<pll> dp(n, {INF, INF});
    vector<bool> vis(n);
    auto dfs = [&](int u, auto &&self) -> void {
        if (vis[u]) return;
        vis[u] = true;
        dp[u] = {dist[0][u], dist[1][u]};
        for (int v : alt[u]) {
            self(v, self);
            for (int id = 0; id < 2; id++) {
                smin(dp[u][id], dp[v][id]);
            }
        }
        for (int id = 0; id < 2; id++) {
            smin(res, dist[id][u] + dp[u][!id]);
        }
    };
    dfs(a[1], dfs);
    cout << res << "\n";
}
/**
 * Construct an alternate graph with all the 
 * edges in possible shortest paths from S to T.
 * Any path from U to V can take any "vertical" path
 * on this alternate graph (b/c it's a DAG). So,
 * consider this alternate graph and DP on the DAG.
*/

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