Submission #1127776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127776		tsengang	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	549 ms	42248 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);
vector<ll> dist(100005, 1e18);
vector<bool> vis(100005, 0);
vector<ll> bef(100005, -1);
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;
    dist[s] = 0;
    st.insert({0, 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[p.ss] + y < dist[x]) {
                dist[x] = dist[p.ss] + y;
                st.insert({dist[x], x});
                bef[x] = p.ss;
            }
        }
    }
    if(u == s){
        vector<ll>dist1(n+5,1e18);
        st.clear();
        fill(all(vis),0);
        dist1[t] = 0;
        st.insert({0,t});
        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 (dist1[p.ss] + y < dist1[x]) {
                    dist1[x] = dist1[p.ss] + y;
                    st.insert({dist1[x], x});
                }
            }
        }
        vector<ll>dist2(n+5,1e18);
        st.clear();
        fill(all(vis),0);
        st.insert({0,v});
        dist2[v] = 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 (dist2[p.ss] + y < dist2[x]) {
                    dist2[x] = dist2[p.ss] + y;
                    st.insert({dist2[x], x});
                }
            }
        }
        for(ll i = 1; i <= n; i++){
            if(dist[i]+dist1[i] == dist[t])ans = min(ans,dist2[i]);
        }
        cout << ans ;
        ertunt 0;
    }
    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: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45