제출 #539426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
539426		Antekb	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	612 ms	23132 KiB

commuter_pass

#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
using ll=long long;
const int N=1e5+5;
const ll INF=1e18;
vector<pair<int, int> > E[N];
int n;
vector<ll> dij(int s){
    vector<ll> dist(n+1, INF);
    vector<bool> vis(n+1);
    dist[s]=0;
    priority_queue<pair<ll, int> > Q;
    for(int i=1; i<=n; i++){
        Q.push({-dist[i], i});
    }
    while(Q.size()){
        //cout<<"a";
        int v=Q.top().nd;
        Q.pop();
        if(vis[v])continue;
        vis[v]=1;
        for(auto u:E[v]){
            if(dist[v]+u.nd<dist[u.st]){
                dist[u.st]=dist[v]+u.nd;
                Q.push({-dist[u.st], u.st});
            }
        }
    }
    return dist;
}
vector<ll> ds,dt,du,dv;
ll opt[N];
int main(){
    int m;
    cin>>n>>m;
    int s, t;
    int U, V;
    cin>>s>>t>>U>>V;
    for(int i=0; i<m; i++){
        int u, v, w;
        cin>>u>>v>>w;
        E[u].push_back({v, w});
        E[v].push_back({u, w});
    }
    ds=dij(s), dt=dij(t), du=dij(U), dv=dij(V);
    //for(auto i:ds)cout<<i<<" ";
    ll ans=du[V];
    vector<int> kol(n);
    for(int i=0; i<n; i++)kol[i]=i+1;
    sort(kol.begin(), kol.end(), [](int a, int b){return ds[a]<ds[b];});
    for(int i=1; i<=n; i++)opt[i]=du[i];
    for(int v:kol){
        for(auto u:E[v]){
            if(dt[v]+ds[u.st]+u.nd==ds[t]){
                opt[v]=min(opt[v], opt[u.st]);
            }
        }
        if(dt[v]+ds[v]==ds[t])ans=min(ans, opt[v]+dv[v]);
    }
    //reverse(kol.begin(), kol.end());
    for(int i=1; i<=n; i++)opt[i]=dv[i];
    for(int v:kol){
        for(auto u:E[v]){
            if(dt[v]+ds[u.st]+u.nd==ds[t]){
                opt[v]=min(opt[v], opt[u.st]);
            }
        }
        //cout<<v<<" "<<opt[v]<<"\n";
        if(dt[v]+ds[v]==ds[t])ans=min(ans, opt[v]+du[v]);
    }
    cout<<ans;
}

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