Submission #1023738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023738		snpmrnhlol	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	464 ms	25312 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5;
const ll inf = 1e18;
vector <pair<ll,ll>> e[N];
vector <ll> dists,distt;
vector <ll> distu,distw;
vector <ll> tmp;
vector <ll> distus,distut;
vector <ll> distws,distwt;
priority_queue <pair<ll,ll>> pq;
ll n,m,u,w,s,t,ans = inf;
void dj(ll source,vector <ll> &dist){
    dist.assign(n,inf);
    dist[source] = 0;
    pq.push({0,source});
    while(!pq.empty()){
        ll d = -pq.top().first;
        ll id = pq.top().second;
        pq.pop();
        if(dist[id] < d)continue;
        for(auto i:e[id]){
            if(dist[i.first] > d + i.second){
                dist[i.first] = d + i.second;
                pq.push({-dist[i.first],i.first});
            }
        }
    }
}
void dj2(ll source,vector <ll> &dist,vector <ll> &distother){
    tmp.assign(n,inf);
    distother.assign(n,inf);
    tmp[source] = 0;
    pq.push({0,source});
    distother[source] = dist[source];
    while(!pq.empty()){
        ll d = -pq.top().first;
        ll id = pq.top().second;
        pq.pop();
        if(tmp[id] < d)continue;
        for(auto i:e[id]){
            if(tmp[i.first] > d + i.second){
                tmp[i.first] = d + i.second;
                pq.push({-tmp[i.first],i.first});
                distother[i.first] = min(distother[id], dist[i.first]);
            }else if(tmp[i.first] == d + i.second){
                distother[i.first] = min(distother[id], distother[i.first]);
            }
        }
    }
}
int main(){
    cin>>n>>m;
    cin>>u>>w;
    cin>>s>>t;
    s--;t--;u--;w--;
    for(ll i = 0;i < m;i++){
        ll a,b,x;
        cin>>a>>b>>x;
        e[a - 1].push_back({b - 1,x});
        e[b - 1].push_back({a - 1,x});
    }
    ///dj from s
    dj(s,dists);
    ///dj from t
    dj(t,distt);
    ///dj from u
    dj(u,distu);
    ///dj from w
    dj(w,distw);
    ///dijkstra 1 from u
    dj2(u,dists,distus);
    ///dijkstra 2 from u
    dj2(u,distt,distut);
    ///dj 1 from w
    dj2(w,dists,distws);
    ///dj 2 from w
    dj2(w,distt,distwt);
    for(ll i = 0;i < n;i++){
        if(distu[i] + distw[i] == distu[w]){
            ///i is one of the bithces
            ans = min(ans, distus[i] + distwt[i]);
            ans = min(ans, distut[i] + distws[i]);
            //cout<<i<<' '<<distus[i]<<' '<<distwt[i]<<'' <<
        }
    }
    ans = min(ans,distt[s]);
    cout<<ans<<'\n';
    return 0;
}

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