Submission #768172

#	Time	Username	Problem	Language	Result	Execution time	Memory
768172		LeoChen112358	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	338 ms	23940 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define pii pair<long,int>
#define piii pair<long,pair<int,int>>
const int Nlim=1e5,Mlim=2e6,Vlim=1e9;
const long INF=(long)Mlim*Vlim+1;
int N,M,S,T,U,V;
vector<pii>conn[Nlim];
long Sdist[Nlim],Udist[Nlim],Vdist[Nlim];
long dp_U[Nlim],dp_V[Nlim];
bool visit[Nlim];

void dijkstra(int start,long dist[]){
	for(int i=0; i<N; i++)dist[i]=INF;
	priority_queue<pii,vector<pii>,greater<pii>>PQ;
	dist[start]=0;
	PQ.push({0,start});
	while(!PQ.empty()){
		long dd=PQ.top().first;
		int node=PQ.top().second;
		PQ.pop();
		if(dist[node]!=dd)continue;//updated by someone else already
		for(auto edge:conn[node]){
			long w=edge.first;
			int nd=edge.second;
			if(dist[nd]>dist[node]+w){
				dist[nd]=dist[node]+w;
				PQ.push({dist[nd],nd});
			}
		}
	}
}
void dijkstra_dp(int start,int end,long dist[]){
	for(int i=0; i<N; i++){
		dist[i]=dp_U[i]=dp_V[i]=INF;
		visit[i]=0;
	}
	priority_queue<piii,vector<piii>,greater<piii>>PQ;
	dist[start]=0;
	PQ.push({0,{start,start}});//cumulative distance, node, parent
	while(!PQ.empty()){
		long dd=PQ.top().first;
		int node=PQ.top().second.first,parent=PQ.top().second.second;
		PQ.pop();
		if(!visit[node]){
			visit[node]=1;
			dist[node]=dd;
			for(auto edge:conn[node]){
				long w=edge.first;
				int nd=edge.second;
				PQ.push({dd+w,{nd,node}});
			}
			dp_U[node]=min(Udist[node],dp_U[parent]);
			dp_V[node]=min(Vdist[node],dp_V[parent]);
		}
		else if(dist[node]==dd){//alternative but equally good route
			long uu=min(Udist[node],dp_U[parent]);
			long vv=min(Vdist[node],dp_V[parent]);
			//we check if the parent is better or not
			//we can't just update one of the DPs as we either choose to use this route or don't
			if(dp_U[node]+dp_V[node]>=uu+vv){//makes the answer better makes the route better
				dp_U[node]=uu;
				dp_V[node]=vv;
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>N>>M;
	cin>>S>>T;
	cin>>U>>V;
	S--,T--,U--,V--;
	for(int i=0; i<M; i++){
		int a,b,c;
		cin>>a>>b>>c;
		a--,b--;
		conn[a].push_back({c,b});
		conn[b].push_back({c,a});//undirected
	}
	dijkstra(U,Udist);
	dijkstra(V,Vdist);
	long ans=Udist[V];
	//construct dp_U, dp_U[i]=min distance from U to an arbitrary someone within S->i
	//dp_U[i]=min(Udist[i],dp_U[i.parent]) I.E. shortest to i vs previous shortest till i.parent
		//construct dp_V similarly
	dijkstra_dp(S,T,Sdist);
	ans=min(ans,dp_U[T]+dp_V[T]);
	dijkstra_dp(T,S,Sdist);//undirected so we also check the opposite direction
	ans=min(ans,dp_U[S]+dp_V[S]);
	cout<<ans<<'\n';
}

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