Submission #1039522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039522		soncao	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	287 ms	29668 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define ii pair<int,int>
#define lll pair<ll,ll>
#define vi vector<int>
#define vvi vector<vector<int>>
int n,m,s,t,u,v;
ll du[100001],dv[100001],ds[100001],dp[2][100001],ans;
bool vs[100001];
vector<lll>a[100001];
void djk1(int st, ll ar[]){
    memset(vs,false,sizeof vs);
    for(int i=1;i<=n;i++)ar[i]=1e14;
    priority_queue<lll>q;
    q.push({0,st});
    ar[st]=0;
    //cout<<st<<'\n';
    while(q.size()){
        ll w=-q.top().first,u=q.top().second;

        q.pop();
        if(vs[u])continue;
        vs[u]=true;
        for(lll it:a[u]){
            int v=it.first,w1=it.second;
            if(ar[v]>w1+w){
                ar[v]=w1+w;
                q.push({-ar[v],v});
            }
        }
    }
}
void djk2(int st,int ed){
    memset(dp,31,sizeof dp);
    memset(vs,false,sizeof vs);
    priority_queue<pair<ll,lll>>q;
    q.push({0,{st,0}});
    while(q.size()){
        ll c=q.top().first,node=q.top().second.first,par=q.top().second.second;
        q.pop();
        if(!vs[node]){
            vs[node]=true;
            ds[node]=-c;
            dp[0][node]=min(du[node],dp[0][par]);
            dp[1][node]=min(dv[node],dp[1][par]);
            for(lll it:a[node])q.push({c-it.second,{it.first,node}});
        }else if(-c==ds[node]){
            if (min(du[node], dp[0][par]) + min(dv[node], dp[1][par]) <=
			    dp[0][node] + dp[1][node]) {
				dp[0][node] = min(du[node], dp[0][par]);
				dp[1][node] = min(dv[node], dp[1][par]);
			}
        }
    }
    ans=min(dp[0][ed]+dp[1][ed],ans);
}
void sc()
{
    cin>>n>>m>>s>>t>>u>>v;
    for(int i=1;i<=m;i++){
        ll U,V,W;cin>>U>>V>>W;
        a[U].push_back({V,W});
        a[V].push_back({U,W});
    }
    djk1(u,du);
    djk1(v,dv);
    ans=du[v];
   // cout<<ans<<'\n';
    djk2(s,t);
    djk2(t,s);
    cout<<ans<<'\n';
}
int main()
{
    ios_base :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
    sc() ;
    return 0 ; ///sc
}

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