Submission #908505

#	Time	Username	Problem	Language	Result	Execution time	Memory
908505		thinknoexit	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	394 ms	30104 KiB

commuter_pass

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

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