Submission #1015964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015964		Kryz	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	255 ms	33404 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define sst string
#define pb push_back
#define maxco 100000+5
#define lld long double
#define cha ios_base::sync_with_stdio(false);
#define ffl cout.flush();
#define phi acos(-1)
#define mr make_pair
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define pqin priority_queue<ll,vector<ll>,greater<>>
#define pqpair priority_queue<pair<ll,ll> ,vector<pair<ll,ll>>,greater<pair<ll,ll>>>
#define pqpair2 priority_queue<pair<pair<ll,ll>,pair<ll,ll>>,vector<pair<pi,pair<ll,ll>>>,greater<pair<pi,pair<ll,ll>>>>
#define INF 1000000009
#define MAXN 200069
#define pii pair<ll,ll>
#define mod 998244353

ll n,m;
ll s,t,u,v;
vector <pii> vec[MAXN];
ll dist[5][MAXN];
vector <ll> bc[MAXN];
bool vis[MAXN];
void djikstra(ll idx,ll in){
    priority_queue<pair<ll,ll> ,vector <pair<ll,ll>>,greater<pair<ll,ll>>> pq;
    pq.push({0,in});
    dist[idx][in]=0;
    while(!pq.empty()){
        ll cost=pq.top().fi;
        ll fr=pq.top().se;
        pq.pop();
        if(cost>dist[idx][fr] )continue;
        if(vis[fr])continue;
        vis[fr]=1;
        if(vec[fr].size()){
            for(auto x : vec[fr]){
                if(dist[idx][x.se]>dist[idx][fr]+x.fi){
                    dist[idx][x.se]=dist[idx][fr]+x.fi;
                    pq.push({dist[idx][x.se],x.se});
                    if(idx==3){
                        bc[x.se].clear();
                        bc[x.se].pb(fr);
                    }
                }
                else if(dist[idx][x.se]==dist[idx][fr]+x.fi){
                    if(idx==3){
                        bc[x.se].pb(fr);
                    }
                }
            }
        }
    }
}
ll dp[MAXN];
int main(){
    cha
    cin>>n>>m;
    cin>>s>>t>>u>>v;
    REP(i,1,4)REP(j,1,n)dist[i][j]=1e18;
    REP(i,1,n)dp[i]=1e18;
    REP(i,1,m){
        ll u,v,w;
        cin>>u>>v>>w;
        vec[u].pb({w,v});
        vec[v].pb({w,u});
    }
    REP(i,1,n)vis[i]=0;
    djikstra(1,u);
    REP(i,1,n)vis[i]=0;
    djikstra(2,v);
    REP(i,1,n)vis[i]=0;
    djikstra(3,s);
    ll ans=1e18;
    priority_queue<pair<pii,pair<ll,ll>> ,vector <pair<pii,pii>>,greater<pair<pii,pii>>> pq;
    pq.push({{dist[1][t]+dist[2][t],t},{dist[1][t],dist[2][t]}});
    dp[t]=dist[1][t]+dist[2][t];
    ans=dp[t];
    while(pq.size()){
        ll node=pq.top().fi.se;
        ll bf1=pq.top().se.fi;
        ll bf2=pq.top().se.se;
        ll cost=pq.top().fi.fi;
        pq.pop();
        if(cost>dp[node] )continue;
        ans=min(ans,dp[node]);
        if(bc[node].size()){
            for(auto x : bc[node]){
                ll nwx=min(bf1,dist[1][x]);
                ll nwy=min(bf2,dist[2][x]);
                if(dp[x]>nwx+nwy){
                    dp[x]=nwx+nwy;
                    pq.push({{dp[x],x},{nwx,nwy}});
                }
            }
        }
    }
    ans=min(dist[1][v],ans);
    cout<<ans<<endl;
    
}

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