Submission #1089711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089711		ocasu	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	439 ms	30484 KiB

commuter_pass

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

#define int long long
int n,m,s,t,u,v; 

vector<vector<pair<int,int>>> adj;

vector<int> distU, distV, dpForward, dpBackward, distS, distT, dS, dT;

void dijkstra1(int node, vector<int>& dist){
    priority_queue<pair<int,int>> pq;
    pq.push({0,node});
    while(!pq.empty()){
        int x=pq.top().second; int d = -pq.top().first; pq.pop();
        if (dist[x] != -1) continue;
        dist[x] = d;
        for (auto [y,w]: adj[x]){
            int tmp=w+d;
            pq.push({-tmp, y});
        }
    }
}


signed main(){
    cin>>n>>m>>s>>t>>u>>v;
    adj.resize(n+1);
    for (int i=0; i<m; i++){
        int x,y,w; cin>>x>>y>>w;
        adj[x].push_back({y,w});
        adj[y].push_back({x,w});
    }
    distU.resize(n+1,-1), distV.resize(n+1, -1), distS.resize(n+1,-1), distT.resize(n+1,-1), dpForward.resize(n+1,-1), dpBackward.resize(n+1,-1);
    dS.resize(n+1,-1), dT.resize(n+1,-1);
    dijkstra1(u, distU);
    dijkstra1(v, distV);
    dijkstra1(s, dS);
    dijkstra1(t, dT);

    vector<bool> vF(n+1,false), vB(n+1,false);
    //now compute dpForward and dpBackward
    priority_queue<pair<int,int>> pq;
    pq.push({0,s});
    dpForward[s] = distV[s];
    while(!pq.empty()){
        auto [d, node] = pq.top();
        pq.pop();
        d*=-1;
        if (vF[node]) continue;
        vF[node]=true;
        for (auto [x,w]: adj[node]){
            int tmp=d+w;
            if (dT[x] != dT[node]-w) continue;

            if (distS[x]==-1){
                dpForward[x] = min(dpForward[node], distV[x]);
                distS[x] = tmp;
            } else if (distS[x] == tmp){
                dpForward[x] = min(dpForward[x], min(dpForward[node],distV[x]));
            } else if (tmp < distS[x]){
                dpForward[x] = min(dpForward[node], distV[x]);
                distS[x] = tmp;
            }
            pq.push({-tmp,x});
        }
    }
    
    pq.push({0,t});
    dpBackward[t] = distV[t];
    while(!pq.empty()){
        auto [d, node] = pq.top();
        pq.pop();
        d*=-1;
        if (vB[node]) continue;
        //cout<<node<<'\n';
        vB[node]=true;
        for (auto [x,w]: adj[node]){
            if (dS[x] != dS[node]-w) continue;

            int tmp=d+w;
            if (distT[x]==-1){
                dpBackward[x] = min(dpBackward[node], distV[x]);
                distT[x] = tmp;
            } else if (distT[x] == tmp){
                dpBackward[x] = min(dpBackward[x], min(dpBackward[node],distV[x]));
            } else if (tmp < distT[x]){
                dpBackward[x] = min(dpBackward[node], distV[x]);
                distT[x] = tmp;
            }
            pq.push({-tmp,x});
        }
    }
    //cout<<'\n';
    int ans=distU[v];
    for (int i=1; i<=n; i++){
        if (vF[i]==false or vB[i]==false) continue;
        //cout<<i<<' '<<dpForward[i]<<' '<<dpBackward[i]<<'\n';
        ans=min(ans, distU[i]+min(dpBackward[i],dpForward[i]));
    }
    cout<<ans<<'\n';


}

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