제출 #1127634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127634		tsengang	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	345 ms	38052 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;
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll n, m;
    cin >> n >> m;
    ll s, t;
    cin >> s >> t;
    ll u, v;
    cin >> u >> v;
    vector<set<pair<ll,ll>>> adj(n+4);
    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, (ll)1e18);
    vector<bool> vis(n+5, 0);
    vector<ll> bef(n+5, -1);
    st.insert({0, s});
    dist[s] = 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++){
        auto it = adj[arr[i]].lower_bound({arr[i-1], 0});
        adj[arr[i]].erase(it);
        it = adj[arr[i-1]].lower_bound({arr[i], 0});
        adj[arr[i-1]].erase(it);
        adj[arr[i-1]].insert({arr[i],0});
        adj[arr[i]].insert({arr[i-1],0});
    }
    fill(all(dist), (ll)1e18);
    st.clear();
    st.insert({0, u});
    fill(all(vis), 0);
    dist[u] = 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});
            }
        }
    }
    cout << dist[v];
}

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