Submission #916328

#	Time	Username	Problem	Language	Result	Execution time	Memory
916328		Maite_Morale	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	878 ms	68012 KiB

commuter_pass

#include<bits/stdc++.h>
#define F first
#define S second
#define MAX 500005
#define oo 1e18
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
using namespace std;
typedef long long ll;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>
 
ll t,n,m,s,s2,e,e2,a1,a2,a3;
ll pass[MAX][10],d[MAX][10],mn[MAX][10];
vpll g[MAX];
void distra(ll x,ll z,ll y){
    priority_queue<pll> q;
    q.push({0,x});
    while(!q.empty()){
        pll u=q.top();q.pop();
        if(pass[u.S][z]!=0)continue;
        pass[u.S][z]=1;
        d[u.S][z]=-u.F;
        //if(u.S==y)return;
        for(auto w: g[u.S]){
            q.push({u.F-w.S,w.F});
        }
    }
}
void distra2(ll x,ll z,ll y,ll o){                                          
    priority_queue<pair<pll,ll>> q;
    q.push({{0,-d[x][o]},x});
    while(!q.empty()){
        pair<pll,ll> u=q.top();q.pop();
        if(pass[u.S][z]!=0)continue;
        pass[u.S][z]=1;
        d[u.S][z]=-u.F.F;
        mn[u.S][o]=min(mn[u.S][o],-u.F.S);
        //if(o==1)cout<<u.S<<" "<<d[u.S][z]<<" "<<mn[u.S][o]<<" "<<u.F.S<<" "<<d[u.S][o]<<"\n";
        if(u.S==y)return;
        for(auto w: g[u.S]){
           // if(w.S==1 && o==1)cout<<-min(d[w.F][o],-u.F.S)<<"\n";
            q.push({{u.F.F-w.S,-min(d[w.F][o],-u.F.S)},w.F});
        }
    }
}
int main(){
    fast_in
    cin>>n>>m>>s>>e>>s2>>e2;
    for(int i=0;i<m;i++){
        cin>>a1>>a2>>a3;
        g[a1].push_back({a2,a3});
        g[a2].push_back({a1,a3});
    }
    for(int i=0;i<=n;i++){
        d[i][0]=d[i][1]=d[i][2]=d[i][3]=d[i][4]=d[i][5]=oo;
        pass[i][0]=pass[i][1]=pass[i][2]=pass[i][3]=pass[i][4]=pass[i][5]=0;
        mn[i][0]=mn[i][1]=oo;
    }
    distra(s2,0,e2);distra(e2,1,s2);
    distra2(s,2,e,0);distra2(e,3,s,1);
    distra2(s,4,e,1);distra2(e,5,s,0);
    ll r=d[e2][0];//cout<<r<<" ";
    for(int i=1;i<=n;i++){
      //  cout<<d[i][1]<<" ";
        if(d[i][4]+d[i][5]==d[e][4]){
           // cout<<i<<" "<<mn[i][0]<<" "<<mn[i][1]<<"\n";
            r=min(r,d[i][0]+mn[i][1]);
        }
    }
    cout<<r<<"\n";
return 0;
}

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