Submission #1050280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050280		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	150 ms	16840 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];
vector<pair<ll,ll>> a[maxn];
set<pair<ll,ll>> ro;

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(ro.count(make_pair(cur,to))){
                        cost=0;
                  }
                  if(ans[cur]+cost<ans[to]){
                        ans[to]=ans[cur]+cost;
                        p[to]=cur;
                        q.push(make_pair(-ans[to],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];
      }
}


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);
}

void subtask2(){
      set_route(f1);
      cl_ans(s2);
      dfs_dj(s2);
      cout<<ans[f2];
}

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);
      
      return 0;
}

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