Submission #93839

#	Time	Username	Problem	Language	Result	Execution time	Memory
93839		brcode	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	702 ms	27492 KiB

commuter_pass

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std;
const long long N = 200100;
long long ans;
priority_queue<pair<long long,long long>> q1;
long long n,m,s,t,a,b;
vector<pair<long long,long long>> v1[N];
bool visited[N];
long long dp[N];
long long ds[N],dt[N],du[N],dv[N];
void dijkstra(long long *d,long long s){
    for(long long i=1;i<=n;i++){
        d[i] = 1e18;
    }
    d[s] = 0;
    q1.push(make_pair(-d[s],s));
    while(!q1.empty()){
        auto hold = q1.top();
        q1.pop();
        for(auto e:v1[hold.second]){
            if(d[e.first]>d[hold.second]+e.second){
                d[e.first] = d[hold.second] + e.second;
                q1.push(make_pair(-1*d[e.first],e.first));
            }
        }
    }
    
}
long long dfs(long long s,long long check){
    if(visited[s]){
        return dp[s];
    }
    visited[s] = true;
    dp[s] = du[s];
    for(auto e:v1[s]){
        if(check == 0){
            if(ds[s]+e.second+dt[e.first] == ds[t]){
                dp[s] = min(dp[s],dfs(e.first,check));
            }
        }else{
            if(dt[s]+e.second+ds[e.first] == ds[t]){
                dp[s] = min(dp[s],dfs(e.first,check));
            }
        }
    }
    ans = min(ans,dp[s]+dv[s]);
    return dp[s];
}
int main() {
    cin>>n>>m>>s>>t>>a>>b;
    for(long long i=1;i<=m;i++){
        long long x,y,z;
        cin>>x>>y>>z;
        v1[x].push_back(make_pair(y,z));
        v1[y].push_back(make_pair(x,z));
    }
    dijkstra(du,a);
    dijkstra(dv,b);
    dijkstra(ds,s);
    dijkstra(dt,t);
    
    ans = du[b];
    dfs(s,0);
    for(long long i=1;i<=n;i++){
        visited[i] = false;
    }
    dfs(t,1);
    cout<<ans<<endl;
}

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