Submission #1032709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032709		warrenn	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	305 ms	32184 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int,int> > adj[100002];
int dis[100002];
int dit[100002];
int ans[100002][4];
priority_queue<tuple<int,int>,vector<tuple<int,int> > , greater<tuple<int,int> > > pq;
priority_queue<tuple<int,int,int>,vector<tuple<int,int,int> > ,greater<tuple<int,int,int> > > last;
int n,m,s,t,u,v;

void djikstra(){
    while(!pq.empty()){
        auto [dist,idx]=pq.top();
        pq.pop();
        if(dist!=dis[idx])continue;

        for(auto r : adj[idx]){
            if(dis[r.first]>dist+r.second){
                dis[r.first]=dist+r.second;
                pq.push({dis[r.first],r.first});
            }
        }
    }
}

void djikstra2(){
    while(!pq.empty()){
        auto [dist,idx]=pq.top();
        pq.pop();
        if(dist!=dit[idx])continue;

        for(auto r : adj[idx]){
            if(dit[r.first]>dist+r.second){
                dit[r.first]=dist+r.second;
                pq.push({dit[r.first],r.first});
            }
        }
    }
}

void jawab(){
    while(!last.empty()){
        auto [dist,idx,type]=last.top();
        last.pop();
        if(dist!=ans[idx][type])continue;

        if(type==0){
            for(auto r : adj[idx]){
                if(ans[r.first][0]>dist+r.second){
                    ans[r.first][0]=dist+r.second;
                    last.push({ans[r.first][0],r.first,0});
                    //cout<<r.first<<" "<<ans[r.first][0]<<" "<<0<<endl;
                }

                if(ans[r.first][1]>dist && dit[idx]+dis[r.first]+r.second==dis[t]){
                    ans[r.first][1]=dist;
                    last.push({ans[r.first][1],r.first,1});
                    //cout<<r.first<<" "<<ans[r.first][1]<<" "<<1<<endl;
                }

                if(ans[r.first][2]>dist && dis[idx]+dit[r.first]+r.second==dis[t]){
                    ans[r.first][2]=dist;
                    last.push({ans[r.first][2],r.first,2});
                    //cout<<r.first<<" "<<ans[r.first][2]<<" "<<2<<endl;
                }

            }
        }
        else if(type==1){
            for(auto r : adj[idx]){
                if(ans[r.first][1]>dist && dit[idx]+dis[r.first]+r.second==dis[t]){
                    ans[r.first][1]=dist;
                    last.push({ans[r.first][1],r.first,1});
                   // cout<<r.first<<" "<<ans[r.first][1]<<" "<<1<<endl;
                }
            }

            for(auto r : adj[idx]){
                if(ans[r.first][3]>dist+r.second){
                    ans[r.first][3]=dist+r.second;
                    last.push({ans[r.first][3],r.first,3});
                }

            }
        }
        else if(type==2){
            for(auto r : adj[idx]){
                if(ans[r.first][2]>dist && dis[idx]+dit[r.first]+r.second==dis[t]){
                    ans[r.first][2]=dist;
                    last.push({ans[r.first][2],r.first,2});
                }
            }

            for(auto r : adj[idx]){
                if(ans[r.first][3]>dist+r.second){
                    ans[r.first][3]=dist+r.second;
                    last.push({ans[r.first][3],r.first,3});
                }
            }
        }
        else if(type==3){
            for(auto r : adj[idx]){
                if(ans[r.first][3]>dist+r.second){
                    ans[r.first][3]=dist+r.second;
                    last.push({ans[r.first][3],r.first,3});
                }
            }
        }
    }
}

signed main(){
    cin>>n>>m>>s>>t>>u>>v;
    for(int q=1;q<=m;q++){
        int a,b,w;
        cin>>a>>b>>w;
        adj[a].push_back({b,w});
        adj[b].push_back({a,w});
    }

    for(int q=1;q<=n;q++){
        ans[q][0]=ans[q][1]=ans[q][2]=ans[q][3]=dis[q]=dit[q]=1e18;
    }
    pq.push({0,s});
    dis[s]=0;
    djikstra();
    pq.push({0,t});
    dit[t]=0;
    djikstra2();
    ans[u][0]=0;

    last.push({0,u,0});

    jawab();
    int maks=1e18;
    for(int q=0;q<=3;q++){
        maks=min(maks,ans[v][q]);
    }
    cout<<maks<<endl;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void djikstra()':
commuter_pass.cpp:14:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |         auto [dist,idx]=pq.top();
      |              ^
commuter_pass.cpp: In function 'void djikstra2()':
commuter_pass.cpp:29:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |         auto [dist,idx]=pq.top();
      |              ^
commuter_pass.cpp: In function 'void jawab()':
commuter_pass.cpp:44:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |         auto [dist,idx,type]=last.top();
      |              ^

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