제출 #335647

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
335647		codebuster_10	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	490 ms	32180 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std ;

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
#define int long long 
#define ld long double
#define f(i,a,b) for(int i=a;i<b;++i)

#define endl '\n'
#define debug cout<<"\n========================================\n";
#define err1(a) cout<<#a<<" "<<a<<endl;
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl;
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl;
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl;

#define PQ priority_queue
#define LB lower_bound  
#define UB upper_bound
#define fr first
#define sc second

#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define show(a) {for(auto xyz:a)cout<<xyz<<" ";cout<<endl;}
#define sz(x) (int)(x).size()

const int INF = 1e16 ;
vector<int> Dijkstra(int n,int src,vector< vector< array<int,2> > > &g){
  PQ<array<int,2> > q ;
  vector<int> dis(n, INF) ;
  dis[src] = 0 ;
  q.push({-dis[src],src}) ;
  while(sz(q)){
    int i = q.top()[1], k = -q.top()[0]  ;
    q.pop() ;
    if( k != dis[i] ){
      continue ;
    } 
    for(auto [j,w]:g[i]){
      if( dis[j] > dis[i] + w ){
        dis[j] = dis[i] + w ;
        q.push({-dis[j],j}) ;
      }
    }
  }
  return dis ;
}
signed main(){
  fastio;
  int N, M, S, T, U, V; 
  cin >> N >> M >> S >> T >> U >> V ;
  --S, --T, --U, --V;
  vector< vector< array<int,2> > > g(N) ;
  f(i,0,M){
    int a, b, c; cin >> a >> b >> c ;
    --a, --b;
    g[a].push_back({b, c});
    g[b].push_back({a, c});
  }
  vector<int> disV = Dijkstra(N,V,g), disS = Dijkstra(N,S,g), disT = Dijkstra(N,T,g), disU = Dijkstra(N,U,g) ;
  vector<int> ComDisV = disV, ComDisV2 = disV  ;
  int MinDis = disT[S] ;
  
  vector< vector<int> > next(N), next2(N) ;
  f(i,0,N){
    for(auto [j, w]:g[i]){
      //does i->j works during S->T
      if( disS[i] + w + disT[j] == MinDis){
        next[i].push_back(j) ;
      }
      //does i->j works during T->S
      if( disT[i] + w + disS[j] == MinDis){
        next2[i].push_back(j) ;
      }
    }
  }
  PQ<array<int,2> > q ;
  f(i,0,N){
    if( sz(next[i]) ){
      q.push({-ComDisV[i], i}) ;
    }
  }
  while(sz(q)){
    int i = q.top()[1] , d = -q.top()[0] ;
    q.pop() ;
    if(d != ComDisV[i]){
      continue ;
    }
    for(auto j:next[i]){
      if(ComDisV[j] > ComDisV[i]){
        ComDisV[j] = ComDisV[i] ;
        q.push({-ComDisV[j], j}) ;
      }
    }
  }
  assert(sz(q) == 0) ;
  f(i,0,N){
    if( sz(next2[i]) ){
      q.push({-ComDisV2[i], i}) ;
    }
  }
  while(sz(q)){
    int i = q.top()[1] , d = -q.top()[0] ;
    q.pop() ;
    if(d != ComDisV2[i]){
      continue ;
    }
    for(auto j:next2[i]){
      if(ComDisV2[j] > ComDisV2[i]){
        ComDisV2[j] = ComDisV2[i] ;
        q.push({-ComDisV2[j], j}) ;
      }
    }
  }
  
  int ans = INF ;
  f(i,0,N){
    ans = min(ans, disU[i] + ComDisV2[i] ) ;
    ans = min(ans, disU[i] + ComDisV[i] ) ;
  }
  cout << ans ;
}

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