Submission #853349

#	Time	Username	Problem	Language	Result	Execution time	Memory
853349		thinknoexit	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	499 ms	34008 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct A {
    int v;
    ll w;
    int p;
    bool operator < (const A& o) const {
        return w > o.w;
    }
};
vector<A> adj[100100];
priority_queue<A> pq;
ll disu[100100], disv[100100], dis[100100];
ll dp[2][100100];
bool vis[100100];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    memset(disu, 0x3f, sizeof disu);
    memset(disv, 0x3f, sizeof disv);
    int n, m;
    cin >> n >> m;
    int s, t, u, v;
    cin >> s >> t >> u >> v;
    while (m--) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        adj[u].push_back({ v,w });
        adj[v].push_back({ u,w });
    }
    disu[u] = 0;
    pq.push({ u,0 });
    while (!pq.empty()) {
        auto x = pq.top();
        pq.pop();
        int v = x.v;
        ll w = x.w;
        for (auto& x : adj[v]) {
            if (disu[x.v] > w + x.w) {
                disu[x.v] = w + x.w;
                pq.push({ x.v,disu[x.v] });
            }
        }
    }
    disv[v] = 0;
    pq.push({ v,0 });
    while (!pq.empty()) {
        auto x = pq.top();
        pq.pop();
        int v = x.v;
        ll w = x.w;
        for (auto& x : adj[v]) {
            if (disv[x.v] > w + x.w) {
                disv[x.v] = w + x.w;
                pq.push({ x.v,disv[x.v] });
            }
        }
    }
    ll ans = disu[v];
    memset(dis, 0x3f, sizeof dis);
    memset(dp, 0x3f, sizeof dp);
    pq.push({ s,0,0 });
    while (!pq.empty()) {
        auto x = pq.top();
        pq.pop();
        int v = x.v, p = x.p;
        ll w = x.w;
        if (!vis[v]) {
            vis[v] = 1;
            dis[v] = w;
            dp[0][v] = min(disv[v], dp[0][p]);
            dp[1][v] = min(disu[v], dp[1][p]);
            for (auto& x : adj[v]) {
                pq.push({ x.v, w + x.w, v });
            }
        }
        else if (w == dis[v]) {
            if (dp[0][v] + dp[1][v] > min(disv[v], dp[0][p]) + min(disu[v], dp[1][p])) {
                dp[0][v] = min(disv[v], dp[0][p]);
                dp[1][v] = min(disu[v], dp[1][p]);
            }
        }
    }
    ans = min(ans, dp[0][t] + dp[1][t]);
    memset(dis, 0x3f, sizeof dis);
    memset(dp, 0x3f, sizeof dp);
    memset(vis, 0, sizeof vis);
    pq.push({ t,0,0 });
    while (!pq.empty()) {
        auto x = pq.top();
        pq.pop();
        int v = x.v, p = x.p;
        ll w = x.w;
        if (!vis[v]) {
            vis[v] = 1;
            dis[v] = w;
            dp[0][v] = min(disv[v], dp[0][p]);
            dp[1][v] = min(disu[v], dp[1][p]);
            for (auto& x : adj[v]) {
                pq.push({ x.v, w + x.w, v });
            }
        }
        else if (w == dis[v]) {
            if (dp[0][v] + dp[1][v] > min(disv[v], dp[0][p]) + min(disu[v], dp[1][p])) {
                dp[0][v] = min(disv[v], dp[0][p]);
                dp[1][v] = min(disu[v], dp[1][p]);
            }
        }
    }
    ans = min(ans, dp[0][s] + dp[1][s]);
    cout << ans;
    return 0;
}

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