Submission #943112

#	Time	Username	Problem	Language	Result	Execution time	Memory
943112		noyancanturk	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	251 ms	25588 KiB

commuter_pass

#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=1e5+500;
#else
    const int lim=3e3+3;
#endif
    
#include "bits/stdc++.h"
using namespace std;
    
#define int int64_t
#define pb push_back
    
const int mod=998244353;
//const int mod=(1ll<<61)-1;

using pii=pair<int,int>;
vector<pii>v[lim];

int n,m;
inline void dj(int s,int*dist){
    for(int i=1;i<=n;i++)dist[i]=LLONG_MAX;
    dist[s]=0;
    priority_queue<pii,vector<pii>,greater<pii>>pq;
    pq.push({0,s});
    while(pq.size()){
        auto [tm,now]=pq.top();
        pq.pop();
        if(tm^dist[now])continue;
        for(auto [j,c]:v[now]){
            if(dist[now]+c<dist[j]){
                dist[j]=dist[now]+c;
                pq.push({dist[j],j});
            }
        }
    }
}

inline void solve(){
    cin>>n>>m;
    int s,t;
    cin>>s>>t;
    int a,b;
    cin>>a>>b;
    for(int i=0;i<m;i++){
        int x,y,c;
        cin>>x>>y>>c;
        v[x].pb({y,c});
        v[y].pb({x,c});
    }
    int dist[n+1],lead[n+1];
    for(int i=0;i<=n;i++){
        dist[i]=LLONG_MAX;
        lead[i]=0;
    }
    dist[s]=lead[s]=0;
    priority_queue<pii,vector<pii>,greater<pii>>pq;
    pq.push({0,s});
    while(pq.size()){
        auto [tm,now]=pq.top();
        pq.pop();
        if(tm^dist[now])continue;
        for(auto [j,c]:v[now]){
            if(dist[now]+c<dist[j]){
                dist[j]=dist[now]+c;
                pq.push({dist[j],j});
                lead[j]=1;
            }else if(dist[now]+c==dist[j]){
                lead[j]++;
            }
        }
    }
    int dista[n+1],distb[n+1],distT[n+1];
    dj(a,dista);
    dj(b,distb);
    dj(t,distT);
    int ans=dista[b],dpa[n+1],dpb[n+1];
    for(int i=0;i<=n;i++){
        dpa[i]=dpb[i]=LLONG_MAX;
    }
    dpa[s]=distb[s];
    dpb[s]=dista[s];
    queue<int>q;
    q.push(s);
    while(q.size()){
        int now=q.front();
        q.pop();
        dpa[now]=min(dpa[now],distb[now]);
        dpb[now]=min(dpb[now],dista[now]);
        ans=min(ans,dpa[now]+dista[now]);
        ans=min(ans,dpb[now]+distb[now]);
        for(auto [j,c]:v[now]){
            if(dist[now]+c+distT[j]==dist[t]){
                dpa[j]=min(dpa[j],dpa[now]);
                dpb[j]=min(dpb[j],dpb[now]);
                if(!(--lead[j])){
                    q.push(j);
                }
            }
        }
    }
    cout<<ans<<"\n";
}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else

#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

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