Submission #590342

#	Time	Username	Problem	Language	Result	Execution time	Memory
590342		Urvuk3	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	373 ms	30972 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll INF=1e9,LINF=1e18,MAXN=1e5+1;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define PRINT(x) cerr<<#x<<'='<<x<<endl;
#define pb push_back
#define PRINTvec(x) { cerr<<#x<<"="; for(int i=0;i<sz(x);i++) cerr<<x[i]<<" "; cerr<<endl; }

int N,M,S,T,U,V;
vector<pair<int,ll>> adj[MAXN];
vector<int> dag[MAXN];
vector<ll> dist1(MAXN),dist2(MAXN),dpU(MAXN,LINF),dpV(MAXN,LINF),dp(MAXN,LINF);
vector<bool> visited(MAXN);
vector<int> topo;

void Dijkstra(int src,vector<ll>& dist){
    for(int i=1;i<=N;i++){
        dist[i]=0;
        visited[i]=0;
    }
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    pq.push({0,src});
    while(!pq.empty()){
        pair<ll,int> vrh=pq.top(); pq.pop();
        if(!visited[vrh.se]){
            visited[vrh.se]=true;
            dist[vrh.se]=vrh.fi;
            for(auto x:adj[vrh.se]){
                if(!visited[x.fi]) pq.push({dist[vrh.se]+x.se,x.fi});
            }
        }
    }
}

void TopoSort(int node){
    visited[node]=true;
    for(auto x:dag[node]) if(!visited[x]) TopoSort(x);
    topo.pb(node);
}

void Solve(){
    cin>>N>>M>>S>>T>>U>>V;
    for(int i=0;i<M;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    Dijkstra(S,dist1);
    Dijkstra(T,dist2);
    for(int i=1;i<=N;i++){
        for(auto x:adj[i]){
            if(dist1[i]+x.se+dist2[x.fi]==dist1[T]){
                dag[i].pb(x.fi);
                //PRINT(i); PRINT(x.fi);
            }
        }
    }
    for(int i=1;i<=N;i++) visited[i]=false;
    TopoSort(S); reverse(all(topo));
    //PRINTvec(topo);
    Dijkstra(U,dist1);
    Dijkstra(V,dist2);
    while(!topo.empty()){
        int node=topo.back(); topo.pop_back();
        //PRINT(node); PRINT(dist1[node]); PRINT(dist2[node]);
        dp[node]=dist1[node]+dist2[node]; //PRINT(dp[node]);
        dpU[node]=dist1[node]; //PRINT(dpU[node]);
        dpV[node]=dist2[node]; //PRINT(dpV[node]);
        for(auto x:dag[node]){
            dpU[node]=min(dpU[node],dpU[x]);
            dpV[node]=min(dpV[node],dpV[x]);
            dp[node]=min(dp[node],dp[x]);
        }
        dp[node]=min({dp[node],dpU[node]+dist2[node],dpV[node]+dist1[node]});
        //PRINT(dp[node]); PRINT(dpU[node]); PRINT(dpV[node]);
    }
    cout<<min(dp[S],dist1[V])<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    //cin>>t;
    t=1;
    while(t--){
        Solve();
    }
    return 0;
}

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