Submission #1273061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273061		kiteyu	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	193 ms	23044 KiB

commuter_pass

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll=long long;
const ll inf=1e18;
const int N=1e5;
int n,m,S,T,U,V;
vector<pair<int,ll>>g[N+5];
ll d[4][N+5];

void dji(int start,int type){
    for(int i=1;i<=n;++i)
        d[type][i]=inf;
    d[type][start]=0;
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>pq;
    pq.push({0,start});
//    cout<<type<<' '<<start<<"->\n";
    while(!pq.empty()){
        pair<ll,int>t=pq.top();
        pq.pop();
        ll w=t.fi;
        int u=t.se;
//        cout<<u<<','<<w<<'\n';
        if(d[type][u]!=w) continue;
        for(pair<int,ll>i:g[u]){
            ll _w=w+i.se;
            if(d[type][i.fi]>_w){
                d[type][i.fi]=_w;
                pq.push({_w,i.fi});
            }
        }
    }
}
int deg[N+5];
ll Dist_V[N+5],Dist_U[N+5];
vector<int>adj[N+5];

void sol(){
    for(int i=1;i<=n;++i){
//        cout<<i<<','<<d[0][i]<<":\n";
        for(pair<int,ll>j:g[i]){
//            cout<<j.fi<<' '<<d[1][j.fi]<<' '<<j.se<<'\n';
            if(d[0][i]+j.se+d[1][j.fi]==d[0][T])
            {
//                cout<<i<<' '<<j.fi<<'\n';
                adj[j.fi].push_back(i);
                deg[i]++;
            }
        }
    }
    queue<int>qe;
    for(int i=1;i<=n;++i){
        if(!deg[i]){
            qe.push(i);
        }
        Dist_V[i]=d[3][i];
        Dist_U[i]=d[2][i];
    }
    ll ans=inf;
    while(!qe.empty()){
        int t=qe.front();
//        cout<<t<<'.'<<Dist_V[t]<<'\n';
        ans=min(ans,Dist_V[t]+d[2][t]);
        ans=min(ans,Dist_U[t]+d[3][t]);
        qe.pop();
        for(int j:adj[t]){
            Dist_V[j]=min(Dist_V[j],Dist_V[t]);
            Dist_U[j]=min(Dist_U[j],Dist_U[t]);
            if(!--deg[j]) qe.push(j);
        }
    }
    cout<<ans;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    cin>>S>>T;
    cin>>U>>V;
    for(int i=1;i<=m;++i){
        int x,y;
        ll w;
        cin>>x>>y>>w;
        g[x].push_back({y,w});
        g[y].push_back({x,w});
    }
    dji(S,0);
    dji(T,1);
    dji(U,2);
    dji(V,3);
    sol();
    return 0;
}

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