Submission #908481

#	Time	Username	Problem	Language	Result	Execution time	Memory
908481		thinknoexit	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	370 ms	29708 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
vector<A> adj[N];
priority_queue<A> pq;
ll solve(int s, int t) {
    memset(dis, 0x3f, sizeof dis);
    for (int i = 1;i <= n;i++) {
        dp[0][i] = dis1[i];
        dp[1][i] = dis2[i];
    }
    dis[s] = 0;
    pq.push({ s, 0, s });
    while (!pq.empty()) {
        auto x = pq.top();
        pq.pop();
        int v = x.v, p = x.p;
        ll w = x.w;
        if (dis[v] != w) continue;
        dp[0][v] = min(dp[0][v], dp[0][p]);
        dp[1][v] = min(dp[1][v], dp[1][p]);
        for (auto& x : adj[v]) {
            if (dis[x.v] > dis[v] + x.w) {
                dis[x.v] = dis[v] + x.w;
                pq.push({ x.v, dis[x.v], v });
            }
        }
    }
    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: 0 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45