제출 #1127772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127772		tsengang	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	359 ms	42384 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);
vodka brgdfs(ll x){
    if(visited[x])ertunt;
    visited[x] = true;
    ans=min(ans,dist[x]);
    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;
    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) {
                    dist[x] = dist[p.ss] + y;
                    st.insert({dist[x], x});
                }
                if(dist[x] == dist[p.ss]+y)beff[x].pb(p.ss);
            }
        }
        st.clear();
        fill(all(vis),0);
        fill(all(dist),1e18);
        dist[v] = 0;
        st.insert({0,v});
        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});
                }
            }
        }
        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