제출 #1133476

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

commuter_pass

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
#define pb push_back
#define ff first
#define ss second
const ll inf = 1e18;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m, s, t, u, v; cin>>n>>m>>s>>t>>u>>v;
    vector<pii> g[n + 1];
    while (m--){
        int x, y, w; cin>>x>>y>>w;
        g[x].pb({y, w});
        g[y].pb({x, w});
    }
    
    vector<int> P(n + 1);
    auto f = [&](int x){
        vector<ll> out(n + 1, inf);
        vector<int> p(n + 1);
        priority_queue<pli, vector<pli>, greater<pli>> pq;
        out[x] = 0; pq.push({0, x});
        while (!pq.empty()){
            auto [d, y] = pq.top(); pq.pop();
            for (auto [i, w]: g[y]){
                ll dd = d + w;
                if (dd < out[i]){
                    out[i] = dd;
                    pq.push({out[i], i});
                    p[i] = y;
                }
            }
        }
        if (x == s) P = p;
        return out;
    };
    
    vector<ll> d[n + 1];
    d[s] = f(s);
    d[t] = f(t);
    d[u] = f(u);
    d[v] = f(v);

    vector<int> G[n + 1];
    for (int i = 1; i <= n; i++){
        G[P[i]].pb(i);
    }
    
    vector<int> tin(n + 1), tout(n + 1);
    int timer = 0;
    function<void(int)> dfs = [&](int v){
        tin[v] = ++timer;
        for (int i: G[v]){
            dfs(i);
        }
        tout[v] = timer;
    };
    dfs(s);
    
    vector<int> a;
    for (int i = 1; i <= n; i++){
        if (d[s][t] == (d[s][i] + d[t][i])){
            a.pb(i);
        }
    }
    
    ll out = d[u][v];
    for (int i: a){
        for (int j: a){
            if (tin[i] <= tin[j] && tout[i] >= tout[j]){
                out = min(out, d[u][i] + d[v][j]);
                out = min(out, d[v][i] + d[u][j]);
            }
        }
    }
    cout<<out<<"\n";
}

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