Submission #136302

#	Time	Username	Problem	Language	Result	Execution time	Memory
136302		KLPP	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	625 ms	69580 KiB

commuter_pass

#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
typedef pair<lld,lld> pii;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
#define INF 10000000000000000
int n,m,s,t,u,v;
vector<pii> nei[1000000];
vector<int> tree[1000000];
lld dist[1000000];
priority_queue<pii> pq;
void calc(int init){
  rep(i,0,n)dist[i]=INF;
  dist[init]=0;
  pq.push(pii(0,init));
  while(!pq.empty()){
    int u=pq.top().second;
    lld d=-pq.top().first;
    pq.pop();
    if(d>dist[u])continue;
    //cout<<u<<" "<<d<<endl;
    trav(V,nei[u]){
      //cout<<v.first<<"A"<<v.second<<" "<<d<<" "<<dist[v.first]<<endl;
      if(dist[V.first]>V.second+d){
	dist[V.first]=V.second+d;
	pq.push(pii(-dist[V.first],V.first));
      }
    }
  }
}
bool visited[1000000];
void Rev(int node){
  visited[node]=true;
  trav(V,nei[node]){
    if(dist[V.first]+V.second==dist[node]){
      tree[node].push_back(V.first);
      if(!visited[V.first])Rev(V.first);
    }
  }
}
lld dist_u[1000000];
lld dist_v[1000000];
lld min_dist_u[1000000];
lld min_dist_v[1000000];
lld calc_u(int node){
  if(min_dist_u[node]!=-1)return min_dist_u[node];
  min_dist_u[node]=dist_u[node];
  trav(V,tree[node]){
    min_dist_u[node]=min(min_dist_u[node],calc_u(V));
  }
  return min_dist_u[node];
}
lld calc_v(int node){
  if(min_dist_v[node]!=-1)return min_dist_v[node];
  min_dist_v[node]=dist_v[node];
  trav(V,tree[node]){
    min_dist_v[node]=min(min_dist_v[node],calc_v(V));
  }
  return min_dist_v[node];
}
int main(){
  
  scanf("%d %d",&n,&m);
  scanf("%d %d",&s,&t);
  s--;t--;
  scanf("%d %d",&u,&v);
  u--;v--;
  rep(i,0,m){
    int x,y;
    lld c;
    scanf("%d %d %lld",&x,&y,&c);
    x--;y--;
    nei[x].push_back(pii(y,c));
    nei[y].push_back(pii(x,c));
  }
  calc(s);
  //rep(i,0,n)cout<<dist[i]<<endl;
  rep(i,0,n){
    visited[i]=false;
  }
  Rev(t);
  /*rep(i,0,n){
    trav(v,tree[i])cout<<v<<" ";
    cout<<endl;
  }*/
  calc(u);
  rep(i,0,n){
    dist_u[i]=dist[i];
    min_dist_u[i]=-1;
  }
  calc(v);
  rep(i,0,n){
    dist_v[i]=dist[i];
    min_dist_v[i]=-1;
  }
  lld ans=dist_u[v];
  rep(i,0,n){
    if(visited[i]){
      calc_u(i);
      calc_v(i);
      ans=min(ans,dist_v[i]+min_dist_u[i]);
      ans=min(ans,dist_u[i]+min_dist_v[i]);
    }
  }
  printf("%lld\n",ans);
  return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n,&m);
   ~~~~~^~~~~~~~~~~~~~~
commuter_pass.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&s,&t);
   ~~~~~^~~~~~~~~~~~~~~
commuter_pass.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~~
commuter_pass.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %lld",&x,&y,&c);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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