Submission #1070291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070291		epicci23	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	309 ms	24928 KiB

commuter_pass

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 1e5 + 5;
const int INF = 1e18;
int n,m,S,T,U,V;
vector<array<int,2>> v[N];
vector<int> dist_S,dist_T,dist_U,dist_V;

vector<int> dijkstra(int st){
  vector<int> dist(N,INF);
  dist[st]=0;
  priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>> pq;
  pq.push({0,st});
  while(!pq.empty()){
  	int d=pq.top()[0],c=pq.top()[1];
  	pq.pop();
  	if(d>dist[c]) continue;
  	for(array<int,2> x:v[c]){
      if(d+x[1]<dist[x[0]]){
      	dist[x[0]]=d+x[1];
      	pq.push({d+x[1],x[0]});
      }
  	} 
  }
  return dist;
}

int Update(){
  int res=INF;
  vector<int> dist(N,INF),ans(N,INF);
  dist[S]=0;
  ans[S]=dist_V[S];
  priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>> pq;
  pq.push({0,S});
  while(!pq.empty()){
  	int d=pq.top()[0],c=pq.top()[1];
  	pq.pop();
  	if(d>dist[c]) continue;
  	ans[c]=min(ans[c],dist_V[c]);
    if(dist[c]+dist_T[c]==dist_S[T]) res=min(res,dist_U[c]+ans[c]);
  	for(array<int,2> x:v[c]){
      if(d+x[1]<dist[x[0]]){
      	dist[x[0]]=d+x[1];
      	ans[x[0]]=ans[c];
      	pq.push({d+x[1],x[0]});
      }
      if(d+x[1]==dist[x[0]]) ans[x[0]]=min(ans[x[0]],ans[c]);
  	} 
  }
  return res;
}

int Update2(){
  int res=INF;
  vector<int> dist(N,INF),ans(N,INF);
  dist[S]=0;
  ans[S]=dist_U[S];
  priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>> pq;
  pq.push({0,S});
  while(!pq.empty()){
  	int d=pq.top()[0],c=pq.top()[1];
  	pq.pop();
  	if(d>dist[c]) continue;
  	ans[c]=min(ans[c],dist_U[c]);
    if(dist[c]+dist_T[c]==dist_S[T]) res=min(res,dist_V[c]+ans[c]);
  	for(array<int,2> x:v[c]){
      if(d+x[1]<dist[x[0]]){
      	dist[x[0]]=d+x[1];
      	ans[x[0]]=ans[c];
      	pq.push({d+x[1],x[0]});
      }
      if(d+x[1]==dist[x[0]]) ans[x[0]]=min(ans[x[0]],ans[c]);
  	} 
  }
  return res;
}


void _(){  
  cin >> n >> m >> S >> T >> U >> V;
  for(int i=0;i<m;i++){
  	int a,b,c;
  	cin >> a >> b >> c;
  	v[a].push_back({b,c});
  	v[b].push_back({a,c});
  }
  dist_S=dijkstra(S),dist_T=dijkstra(T),dist_U=dijkstra(U),dist_V=dijkstra(V);
  int Ans=dist_U[V];
  Ans=min(Ans,Update());
  Ans=min(Ans,Update2());
  cout << Ans << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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