Submission #1050258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050258		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2095 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=100001;
const ll inf=999999999999999999;
ll n,m,s1,f1,s2,f2,ans[maxn],p[maxn];
bool was[maxn];
vector<pair<ll,ll>> a[maxn];
set<pair<ll,ll>> ro;
vector<ll> vp[maxn];

bool change_p=true;

void dfs_dj(ll v){
      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(ans[cur]!=cur_ans)continue;
            for(ll i=0;i<int(a[cur].size());i++){
                  ll to=a[cur][i].first,cost=a[cur][i].second;
                  if(p[cur]==to)continue;
                  if(ro.count(make_pair(cur,to))){
                        cost=0;
                  }
                  if(ans[cur]+cost<=ans[to]){
                        if(change_p){
                              if(ans[to]>ans[cur]+cost){
                                    vp[to].clear();
                              }
                              vp[to].push_back(cur);
                              p[to]=cur;
                        }
                        
                        ans[to]=ans[cur]+cost;
                        q.push(make_pair(-ans[to],to));
                  }
            }
      }
}


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

void go(ll v){
      cl_ans(v);
      dfs_dj(v);
}

ll final_ans=inf;
void set_was(ll v){
      was[v]=1;
      for(ll i=0;i<int(vp[v].size());i++){
            ll to=vp[v][i];
            if(!was[to]){
                  set_was(to);
            }
      }
}



int main(){
      cin>>n>>m>>s1>>f1>>s2>>f2;
      ll st,ft,c;
      for(int i=0;i<m;i++){
            cin>>st>>ft>>c;
            a[st].push_back(make_pair(ft,c));
            a[ft].push_back(make_pair(st,c));
      }
      go(s1);
      set_was(f1);
      change_p=false;
      ll final_ans=inf;
      for(ll i=1;i<=n;i++){
            if(was[i]){
                  go(i);
                  final_ans=min(final_ans,ans[f2]);
            }
      }
      cout<<final_ans;
      return 0;
}

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