Submission #1127769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127769		tsengang	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	2098 ms	53940 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define vodka void
#define ertunt return
using namespace std;
ll n, m, s, t, u, v;
vector<set<pair<ll, ll>>> adj(100004);
ll ans = 1e18;
vector<ll> beff[100004];
vector<bool> visited(100004, 0);
vodka brgdfs(ll x) {
    if (visited[x] == 1) {
        ertunt;
    }
    visited[x] = 1;
    set<pair<ll, ll>> st;
    vector<ll> dist(100005, 1e18);
    vector<bool> vis(100005, 0);
    st.insert({0, x});
    dist[x] = 0;

    while (!st.empty()) {
        pair<ll, ll> p = *st.begin();
        st.erase(p);
        if (vis[p.ss]) continue;
        vis[p.ss] = 1;

        for (auto [y, z] : adj[p.ss]) {
            if (dist[p.ss] + z < dist[y]) {
                dist[y] = dist[p.ss] + z;
                st.insert({dist[y], y});
            }
        }
    }

    ans = min(ans, dist[v]);
    for (auto y : beff[x]) brgdfs(y);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> s >> t >> u >> v;
    for (ll i = 0; i < m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        adj[a].insert({b, c});
        adj[b].insert({a, c});
    }
    set<pair<ll, ll>> st;
    vector<ll> dist(n + 5, 1e18);
    vector<bool> vis(n + 5, 0);
    vector<ll> bef(n + 5, -1);
    dist[s] = 0;
    st.insert({0, s});
    if (u == s) {
        while (!st.empty()) {
            pair<ll, ll> p = *st.begin();
            st.erase(p);
            if (vis[p.ss]) continue;
            vis[p.ss] = 1;
            for (auto [x, y] : adj[p.ss]) {
                if (dist[x] >= dist[p.ss] + y) {
                    beff[x].pb(p.ss);
                    dist[x] = dist[p.ss] + y;
                    st.insert({dist[x], x});
                }
            }
        }
        brgdfs(t);
        cout << ans;
        ertunt 0;
    }
    while (!st.empty()) {
        pair<ll, ll> p = *st.begin();
        st.erase(p);
        if (vis[p.ss]) continue;
        vis[p.ss] = 1;
        for (auto [x, y] : adj[p.ss]) {
            if (dist[p.ss] + y < dist[x]) {
                dist[x] = dist[p.ss] + y;
                st.insert({dist[x], x});
                bef[x] = p.ss;
            }
        }
    }
    vector<ll> arr;
    ll cur = t;
    while (cur > 0) {
        arr.pb(cur);
        cur = bef[cur];
    }
    reverse(all(arr));
    for (ll i = 1; i < arr.size(); i++) {
        ll a = arr[i - 1], b = arr[i];
        auto it = adj[a].lower_bound({b, -1});
        if (it != adj[a].end() && it->ff == b) adj[a].erase(it);
        it = adj[b].lower_bound({a, -1});
        if (it != adj[b].end() && it->ff == a) adj[b].erase(it);
        adj[a].insert({b, 0});
        adj[b].insert({a, 0});
        beff[b].pb(a);
    }
    fill(all(dist), 1e18);
    st.clear();
    dist[u] = 0;
    fill(all(vis), 0);
    st.insert({0, u});
    while (!st.empty()) {
        pair<ll, ll> p = *st.begin();
        st.erase(p);
        if (vis[p.ss]) continue;
        vis[p.ss] = 1;

        for (auto [x, y] : adj[p.ss]) {
            if (dist[p.ss] + y < dist[x]) {
                dist[x] = dist[p.ss] + y;
                st.insert({dist[x], x});
            }
        }
    }
    cout << dist[v];
}

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