Submission #1050591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050591		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	760 ms	262144 KiB

commuter_pass

#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<set>
using namespace std;
 
#define ll long long

const ll maxn=100011;
const ll inf=999999999999999999;

ll n,m,s1,f1,s2,f2,ans[3][maxn],min_d[3][maxn];
vector<pair<ll,ll>> a[maxn];
vector<ll> p[maxn],b[maxn];
bool was[maxn];

void dj(ll v,ll ans_co){
      priority_queue<pair<ll,ll>> q;
      q.push(make_pair(0,v));
      while(!q.empty()){
            ll cur_ans=-q.top().first,cur=q.top().second;
            q.pop();
            if(cur_ans!=ans[ans_co][cur])continue;
            for(auto [to,cost] : a[cur]){
                  if(ans[ans_co][cur]+cost<=ans[ans_co][to]){
                        if(ans_co==0){
                              if(ans[ans_co][cur]+cost<ans[ans_co][to])p[to].clear();
                              if(to!=cur)p[to].push_back(cur);
                        }
                        ans[ans_co][to]=ans[ans_co][cur]+cost;
                        q.push(make_pair(-ans[ans_co][to],to));
                  }
            }
      }
}

void cl_was(){
      for(ll i=1;i<=n;i++)was[i]=0;
}

void cl_ans(ll v,ll ans_co){
      for(ll i=1;i<=n;i++)ans[ans_co][i]=inf;
      ans[ans_co][v]=0;
}

void go(ll v,ll ans_co){
      cl_ans(v,ans_co);
      dj(v,ans_co);
}

void build_b(ll cur){
      was[cur]=1;
      for(auto to : p[cur]){
            if(was[to])continue;
            b[to].push_back(cur);
            build_b(to);
      }
}

void go_b(ll cur,ll prev){
      was[cur]=1;
      min_d[1][cur]=ans[1][cur];
      min_d[2][cur]=ans[2][cur];
      min_d[1][cur]=min(min_d[1][cur],min_d[1][prev]);
      min_d[2][cur]=min(min_d[2][cur],min_d[2][prev]);
      for(auto to : b[cur]){
            if(!was[to])go_b(to,cur);
      }
}


ll get_ans(ll cur){
      was[cur]=1;
      ll cur_ans=min_d[1][cur]+min_d[2][cur];
      //cout<<cur<<' '<<min_d[1][cur]<<'='<<min_d[2][cur]<<endl;
      for(auto to : b[cur]){
            if(was[to])continue;
            cur_ans=min(cur_ans,get_ans(to));
      }
      return cur_ans;
}

int main(){
      cin>>n>>m>>s1>>f1>>s2>>f2;
      ll st,ft,c;
      for(ll i=0;i<m;i++){
            cin>>st>>ft>>c;
            a[ft].push_back(make_pair(st,c));
            a[st].push_back(make_pair(ft,c));
      }
      go(s1,0);
      go(s2,1);
      go(f2,2);
      build_b(f1);
      cl_was();
      go_b(s1,s1);
      cl_was();
      ll final_ans=ans[1][f2];
      cout<<min(get_ans(s1),final_ans)<<endl;
      return 0;
}

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