Submission #1050250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050250		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	683 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=1;
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(ans[to]>ans[cur]+cost and change_p){
                              vp[to].clear();
                        }
                        ans[to]=ans[cur]+cost;
                        if(change_p){
                              vp[to].push_back(cur);
                              p[to]=cur;
                        }
                        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);
            }
      }
}

void set_route(ll v){
      ro.clear();
      while(p[v]!=v){
            ro.insert(make_pair(p[v],v));
            ro.insert(make_pair(v,p[v]));
            v=p[v];
      }
}

bool check_uniq(ll cur){
      if(p[cur]==cur)return true;
      if(vp[cur].size()>1)return false;
      return check_uniq(vp[cur][0]);
}

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));
      }
      
      p[s1]=s1;
      go(s1);
      change_p=false;
      //bool uniq_route=check_uniq(f1);
      if(false){
            final_ans=inf;
            set_was(f1);
            for(ll i=1;i<=n;i++){
                  if(was[i]){
                        go(i);
                        final_ans=min(final_ans,ans[f2]);
                  }
            }
            cout<<final_ans;
      }else{
            set_route(f1);
            cl_ans(s2);
            dfs_dj(s2);
            cout<<ans[f2];
      }
      return 0;
}

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