제출 #1310713

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310713		syanvu	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	2096 ms	40108 KiB

commuter_pass

// #pragma optimize ("g",on)
// #pragma GCC optimize ("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC optimize ("03")
#include <bits/stdc++.h>

#define pb push_back
#define SS ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define int long long
#define all(v) v.begin(),v.end()
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int N = 2e5 + 1, inf = 1e18, mod = 998244353;

vector<array<int, 3>> g[N];
int ok[N], tin[N], tout[N], timer, used[N];
vector<vector<int>> p;
vector<array<int, 3>> e(N);

void f(int v, int r){
    if(v == r){
        ok[v] = 1;
        return;
    }
    for(int to : p[v]){
        tin[to] = ++timer;
        int nxt = (e[to][0] != v ? e[to][0] : e[to][1]);
        f(nxt, r);
        tout[to] = timer;
        if(ok[nxt]) used[to] = 1;
        ok[v] = max(ok[v], ok[nxt]);
        // break;
    }
}
bool ch(int u, int v){
    return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}

void solve(){
    int n, m;
    cin >> n >> m;
    p.resize(n + 1);
    int s, t;
    cin >> s >> t;
    int u, v;
    cin >> u >> v;
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        e[i] = {u, v, w};
        g[u].push_back({v, w, i});
        g[v].push_back({u, w, i});
    }
    vector<int> dist(n + 1, inf);
    priority_queue<pair<int, int>> q;
    q.push({0, s});
    dist[s] = 0;
    while(q.size()){
        auto [musor, v] = q.top();
        q.pop();
        musor = -musor;
        if(musor != dist[v]) continue;
        for(auto [to, w, id] : g[v]){
            if(dist[to] == dist[v] + w) p[to].push_back(id);
            else if(dist[to] > dist[v] + w){
                p[to].clear();
                p[to].push_back(id);
                dist[to] = dist[v] + w;
                q.push({-dist[to], to});
            }
        }
    }
    f(t, s);
    vector<int> tp(n + 1, 0ll);
    dist.assign(n + 1, inf);
    dist[u] = 0;
    set<array<int, 3>> st;
    st.insert({0, 0, u});
    while(st.size()){
        auto [c, t, v] = *st.begin();
        st.erase(st.begin());
        for(auto [to, w, id] : g[v]){
            if(!used[id] && dist[to] > dist[v] + w){
                st.erase({dist[to], tp[to], to});
                dist[to] = dist[v] + w;
                tp[to] = tp[v];
                st.insert({dist[to], tp[to], to});
            }
            else{
                if(tp[v] == 0 && dist[to] > dist[v]){
                    tp[v] = id;
                    st.erase({dist[to], tp[to], to});
                    dist[to] = dist[v];
                    tp[to] = tp[v];
                    st.insert({dist[to], tp[to], to});
                }
                else{
                    if(ch(id, tp[v]) || ch(tp[v], id)){
                        if(dist[to] > dist[v]){
                            tp[v] = id;
                            st.erase({dist[to], tp[to], to});
                            dist[to] = dist[v];
                            tp[to] = tp[v];
                            st.insert({dist[to], tp[to], to});
                        }
                    }
                    else if(dist[to] > dist[v] + w){
                        st.erase({dist[to], tp[to], to});
                        dist[to] = dist[v] + w;
                        tp[to] = tp[v];
                        st.insert({dist[to], tp[to], to});
                    }
                }
            }
        }
    }
    cout << dist[v] << '\n';
    /*
    pref[i] = max(pref[i], pref[i - 1])
    pref[i] - pref[i - 1]
    */
    // for(int i = 1; i <= m; i++){
    //     if(used[i]) cout << tin[i] << ' ' << tout[i] << ' ' << i << '\n';
    // }
}

signed main(){
    SS
    // freopen("trains.in", "r", stdin);
    // freopen("trains.out", "w", stdout);

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

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