Submission #1156960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156960		irmuun	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	193 ms	21012 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
#define pll pair<ll,ll>

const ll N=1e5+5;

ll n,m,S,T,U,V;
ll dp[N][4];
ll dist[N][3];
vector<pll>g[N];

void dijkstra(ll st,ll d){//start node, dist[ ][d]
    priority_queue<pll,vector<pll>,greater<pll>>pq;
    pq.push({0,st});
    dist[st][d]=0;
    while(!pq.empty()){
        auto [ds,x]=pq.top();
        pq.pop();
        if(dist[x][d]!=ds) continue;
        for(auto [y,w]:g[x]){
            if(ds+w<dist[y][d]){
                dist[y][d]=ds+w;
                pq.push({dist[y][d],y});
            }
        }
    }
}

ll get(ll x,ll v){
    ll res=0;
    if(v&1) res+=dist[x][1];
    if(v&2) res+=dist[x][2];
    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    cin>>S>>T>>U>>V;
    for(ll i=1;i<=m;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        g[a].pb({b,c});
        g[b].pb({a,c});
    }
    for(ll i=1;i<=n;i++){
        for(ll j=0;j<3;j++){
            dist[i][j]=(ll)1e18;
        }
    }
    dijkstra(S,0);
    dijkstra(U,1);
    dijkstra(V,2);
    for(ll i=1;i<=n;i++){
        for(ll j=0;j<4;j++){
            dp[i][j]=(ll)1e18;
        }
    }
    pll ds[n+5];
    for(ll i=1;i<=n;i++){
        ds[i]={dist[i][0],i};
    }
    sort(ds+1,ds+n+1,[&](pll a,pll b){
        return a.ff<b.ff;
    });
    dp[S][0]=0;
    dp[S][1]=dist[S][1];//S->x->i baih min of dis(x,U) - dp[i][1]
    dp[S][2]=dist[S][2];//S->y->i baih min of dis(y,V) - dp[i][2]
    dp[S][3]=dist[S][1]+dist[S][2];//S->x->y->i baih min of dis(x,U)+dis(y,V) - dp[i][3]
    for(ll z=1;z<=n;z++){
        ll i=ds[z].ss;
        for(auto [j,w]:g[i]){
            if(dist[i][0]+w!=dist[j][0]) continue; // not shortest
            for(ll l=0;l<4;l++){
                for(ll k=0;k<4;k++){
                    dp[j][l|k]=min(dp[j][l|k],dp[i][l]+get(j,k));
                }
            }
        }
    }
    ll ans=min(dp[T][3],dist[V][1]);
    cout<<ans;
}

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