Submission #1308194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308194		vaishakhv	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	742 ms	39500 KiB

commuter_pass

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll cap = 2e5+1;
const ll INF = (ll)1e18;

vector<pair<ll,ll>> adj[cap];
vector<ll> dag[cap], rdag[cap];
ll indegree[cap];

ll distS[cap], distU[cap], distV[cap];
vector<tuple<ll,ll,ll>> edges;

priority_queue<pair<ll,ll>> pqs, pqu, pqv;

ll n, m;
ll s, t, u, v;

void dijkstra(){
    pqs.push({0,s});
    while(!pqs.empty()){
        auto [nd,x] = pqs.top(); pqs.pop();
        ll d = -nd;
        if(d != distS[x]) continue;
        for(auto [y,w]: adj[x]){
            if(distS[x] + w < distS[y]){
                distS[y] = distS[x] + w;
                pqs.push({-distS[y], y});
            }
        }
    }

    pqu.push({0,u});
    while(!pqu.empty()){
        auto [nd,x] = pqu.top(); pqu.pop();
        ll d = -nd;
        if(d != distU[x]) continue;
        for(auto [y,w]: adj[x]){
            if(distU[x] + w < distU[y]){
                distU[y] = distU[x] + w;
                pqu.push({-distU[y], y});
            }
        }
    }

    pqv.push({0,v});
    while(!pqv.empty()){
        auto [nd,x] = pqv.top(); pqv.pop();
        ll d = -nd;
        if(d != distV[x]) continue;
        for(auto [y,w]: adj[x]){
            if(distV[x] + w < distV[y]){
                distV[y] = distV[x] + w;
                pqv.push({-distV[y], y});
            }
        }
    }
}

ll solve(){
    for(ll i=1;i<=n;i++){
        dag[i].clear();
        rdag[i].clear();
        indegree[i]=0;
    }
    fill(distS,distS+cap,INF);
    fill(distU,distU+cap,INF);
    fill(distV,distV+cap,INF);
    while(!pqs.empty()) pqs.pop();
    while(!pqu.empty()) pqu.pop();
    while(!pqv.empty()) pqv.pop();

    distS[s]=0;
    distU[u]=0;
    distV[v]=0;
    dijkstra();

    for(auto [a,b,w]: edges){
        if(distS[a]+w==distS[b]){
            dag[a].push_back(b);
            rdag[b].push_back(a);
        }
        if(distS[b]+w==distS[a]){
            dag[b].push_back(a);
            rdag[a].push_back(b);
        }
    }

    vector<char> good(n+1,0);
    queue<ll> qq;
    good[t]=1;
    qq.push(t);
    while(!qq.empty()){
        ll x=qq.front(); qq.pop();
        for(ll y: rdag[x]){
            if(!good[y]){
                good[y]=1;
                qq.push(y);
            }
        }
    }

    for(ll i=1;i<=n;i++){
        if(!good[i]) continue;
        for(ll j: dag[i]){
            if(good[j]) indegree[j]++;
        }
    }

    queue<ll> q;
    vector<ll> topo;
    for(ll i=1;i<=n;i++){
        if(good[i] && indegree[i]==0) q.push(i);
    }
    while(!q.empty()){
        ll x=q.front(); q.pop();
        topo.push_back(x);
        for(ll y: dag[x]){
            if(!good[y]) continue;
            if(--indegree[y]==0) q.push(y);
        }
    }

    vector<ll> dp_entry(n+1,INF), dp_ans(n+1,INF);
    for(ll x: topo){
        dp_entry[x]=min(dp_entry[x],distU[x]);
        dp_ans[x]=min(dp_ans[x],dp_entry[x]+distV[x]);
        for(ll y: dag[x]){
            if(!good[y]) continue;
            dp_entry[y]=min(dp_entry[y],dp_entry[x]);
            dp_ans[y]=min(dp_ans[y],dp_ans[x]);
        }
    }

    ll best = min(distU[v], dp_ans[t]);

    for (ll i = 1; i <= n; i++) {
        if (good[i]) best = min(best, distU[i] + distV[i]);
    }

    for (auto [a,b,w] : edges) {
        if (good[a] && good[b]) {
            best = min(best, distU[a] + distV[b]);
            best = min(best, distU[b] + distV[a]);
        }
    }

    return best;
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m;
    cin>>s>>t>>u>>v;
    for(ll i=0;i<m;i++){
        ll a,b,w; cin>>a>>b>>w;
        adj[a].push_back({b,w});
        adj[b].push_back({a,w});
        edges.push_back({a,b,w});
    }

    ll ans1 = solve();
    swap(s,t);
    swap(u,v);
    ll ans2 = solve();

    cout << min(ans1, ans2);
}

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