Submission #1009759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009759		devariaota	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	358 ms	25408 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std; 
#define int long long 
#define ld long double
#define fi first 
#define se second 
#define pb push_back
#define pii pair<int,int>
#define piii pair<pair<int,int>,pair<int,int>>
#define pip pair<int,pair<int,int>>
vector<pii>adj[100005]; 
int dis[100005]; 
int disu[100005], disv[100005]; 
vector<int>bef[100005]; 
bool vis[100005]; 
signed main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL); 
    int n, m; cin >> n >> m; 
    int s,t; cin >> s >> t; 
    int u,v; cin >> u >> v; 
    for(int i = 1; i <= m; i++){
        int x, y, w; cin >> x >> y >> w; 
        adj[x].pb({y,w}); 
        adj[y].pb({x,w}); 
    }

    priority_queue<pii, vector<pii>, greater<pii>>pq; 
    pq.push({0,u}); 
    for(int i = 1; i <= n; i++)disu[i] = 1e18; 
    disu[u] = 0; 
    while(!pq.empty()){
        int jarak = pq.top().fi, node = pq.top().se; 
        pq.pop(); 
        if(jarak != disu[node])continue; 
        for(auto it : adj[node]){
            int curr = jarak + it.se; 
            if(curr < disu[it.fi]){
                disu[it.fi] = curr; 
                pq.push({curr, it.fi}); 
            }
        }
    }
    pq.push({0,v}); 
    for(int i = 1; i <= n; i++)disv[i] = 1e18; 
    disv[v] = 0; 
    while(!pq.empty()){
        int jarak = pq.top().fi, node = pq.top().se; 
        pq.pop(); 
        if(jarak != disv[node])continue; 
        for(auto it : adj[node]){
            int curr = jarak + it.se; 
            if(curr < disv[it.fi]){
                disv[it.fi] = curr; 
                pq.push({curr, it.fi}); 
            }
        }
    }

    for(int i = 1; i <= n; i++)dis[i] = 1e18; 
    dis[s] = 0; 
    priority_queue<pip,vector<pip>,greater<pip>>peq; 
    peq.push({0,{s, -1}});  
    while(!peq.empty()){
        int jarak = peq.top().fi, node = peq.top().se.fi, par = peq.top().se.se; 
        peq.pop(); 
        if(jarak != dis[node])continue; 
        if(par != -1){
            bef[node].pb(par); 
        }
        //cout << "here >> " << node << " " << disu[node] << " " << disv[node] << endl;  
        if(node == t)break; 
        for(auto it : adj[node]){
            int curr = jarak + it.se; 
            if(curr < dis[it.fi]){
                bef[it.fi].clear();
                dis[it.fi] = curr; 
                peq.push({curr, {it.fi, node}}); 
            }
            if(curr == dis[it.fi]){
                bef[it.fi].pb(node); 
            }
        }
    }

    while(!peq.empty()){
        int jarak = peq.top().fi, node = peq.top().se.fi, par = peq.top().se.se;
        peq.pop();
        if(node == t && jarak == dis[t] && par != -1){
            bef[node].pb(par); 
        }
    }
    priority_queue<piii, vector<piii>, greater<piii>>q;
    q.push({{disu[t] + disv[t], t}, {disu[t],disv[t]}}); 
    for(int i = 1; i <= n; i++)dis[i] = 1e18; 
    dis[t] = disu[t] + disv[t]; 
    int ans = disu[v]; 

    while(!q.empty()){  
        int node = q.top().fi.se, jarak = q.top().fi.fi, valu = q.top().se.fi, valv = q.top().se.se; 
        //cout << "here >> " << node << endl; 
        q.pop(); 
        if(jarak != dis[node])continue;  
        if(node == s){
            //cout << "here" << endl; 
            ans = min(ans, jarak); 
            continue; 
        }
        for(auto it : bef[node]){
            //cout << "here1 >> " << it << endl; 
            int curr = min(jarak, min(valu, disu[it]) + min(valv, disv[it]));
            if(curr < dis[it]){
                //cout << "here >> " << it << endl; 
                dis[it] = curr;
                q.push({{curr, it}, {min(valu, disu[it]), min(valv, disv[it])}});
            }
        }
    }
    cout << ans << endl;
}

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