Submission #1277330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277330		shirokito	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	242 ms	23532 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 2e5 + 24;
const ll INF = 1e18;

int n, m, S, T, U, V;
vector<pair<ll, ll>> g[N];
vector<ll> distU, distV, distS;
ll dpU[N], dpV[N];

void gen_dist(int start, vector<ll> &dist) {
    dist.assign(n + 1, INF);
    dist[start] = 0;

    vector<bool> vis(n + 1, 0);

    multiset<pair<ll, ll>> mts;
    mts.insert({0, start});

    while (mts.size()) {
        auto node = *mts.begin();
        mts.erase(mts.find(node));
        int u = node.second;

        if (vis[u]) continue;
        vis[u] = 1;

        for (auto [v, w]: g[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                mts.insert({dist[v], v});
            }
        }
    }

    // cout << start << '\n';
    // for  (int i = 1; i <= n; i++) {
    //     cout << i << ' ' << dist[i] << '\n';
    // }
}

void dfs(int u) {
    if (dpU[u] != INF) return;  
    dpU[u] = distU[u];
    dpV[u] = distV[u];

    for (auto [v, w]: g[u]) {
        if (distS[v] + w == distS[u]) {
            dfs(v);
            dpU[u] = min(dpU[u], dpU[v]);
            dpV[u] = min(dpV[u], dpV[v]);
        }
    }
}

void solve() {
    cin >> n >> m >> S >> T >> U >> V;

    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    gen_dist(S, distS);
    gen_dist(U, distU);
    gen_dist(V, distV);

    fill(dpU, dpU + n + 1, INF);
    fill(dpV, dpV + n + 1, INF);

    dfs(T);

    ll res = INF;
    for (int i = 1; i <= n; i++) {
        res = min(res, dpU[i] + distV[i]);
        res = min(res, dpV[i] + distU[i]);
    }

    cout << res << '\n';
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);

    int TC = 1; // cin >> TC;
    while (TC--) {
        solve();
    }
}

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