Submission #1308188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308188		vaishakhv	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	460 ms	34516 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;

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

ll distS[cap];
ll distU[cap];
ll distV[cap];

vector<tuple<ll,ll,ll>> edges;
priority_queue<pair<ll,ll>> pqs;
priority_queue<pair<ll,ll>> pqu;
priority_queue<pair<ll,ll>> pqv;

ll s, t, u, v;

void dijkstra(){
    pqs.push({0,s});
    while(!pqs.empty()){
        pair<ll,ll> info = pqs.top(); pqs.pop();
        ll d = -1*info.first, n = info.second;
        if (d != distS[n]) continue;
        for (auto nxt: adj[n]){
            if (distS[n] + nxt.second < distS[nxt.first]){
                distS[nxt.first] = distS[n] + nxt.second;
                pqs.push({-distS[nxt.first], nxt.first});
            }
        }
    }

    pqu.push({0,u});
    while(!pqu.empty()){
        pair<ll,ll> info = pqu.top(); pqu.pop();
        ll d = -1*info.first, n = info.second;
        if (d != distU[n]) continue;
        for (auto nxt: adj[n]){
            if (distU[n] + nxt.second < distU[nxt.first]){
                distU[nxt.first] = distU[n] + nxt.second;
                pqu.push({-distU[nxt.first], nxt.first});
            }
        }
    }

    pqv.push({0,v});
    while(!pqv.empty()){
        pair<ll,ll> info = pqv.top(); pqv.pop();
        ll d = -1*info.first, n = info.second;
        if (d != distV[n]) continue;
        for (auto nxt: adj[n]){
            if (distV[n] + nxt.second < distV[nxt.first]){
                distV[nxt.first] = distV[n] + nxt.second;
                pqv.push({-distV[nxt.first], nxt.first});
            }
        }
    }
}


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

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

    for (ll i{}; 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});
    }
    
    fill(distS, distS+cap, 1e18);
    fill(distU, distU+cap, 1e18);
    fill(distV, distV+cap, 1e18);
    fill(indegree, indegree+cap, 0);

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

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

    queue<ll> q;
    vector<ll> sorted;

    for (ll i = 1; i <= n; i++){
        if (indegree[i] == 0 && distS[i] != 1e18) q.push(i);
    }

    while(!q.empty()){
        ll fr = q.front(); q.pop();
        sorted.push_back(fr);
        for (auto nxt: dag[fr]){
            indegree[nxt]--;
            if (indegree[nxt] == 0) q.push(nxt);
        }
    }

    vector<ll> dp_entry(n+1, 1e18);
    vector<ll> dp_answer(n+1, 1e18);

    for (auto n: sorted){
        dp_entry[n] = min(distU[n], dp_entry[n]);
        dp_answer[n] = min(dp_answer[n], dp_entry[n] + distV[n]);
        for (auto nxt: dag[n]){
            dp_entry[nxt] = min(dp_entry[nxt], dp_entry[n]);
            dp_answer[nxt] = min(dp_answer[nxt], dp_answer[n]);
        }
    }

    cout << min(distU[v], dp_answer[t]);
}

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