Submission #209856

#	Time	Username	Problem	Language	Result	Execution time	Memory
209856		kshitij_sodani	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	484 ms	30436 KiB

commuter_pass

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef int64_t llo;
#define a first
#define  b second
#define endl "\n"
vector<pair<llo,llo>> adj[100001];
//vector<pair<llo,llo>> adj2[100001];
vector<pair<llo,llo>> adj3[100001];
llo dis3[100001];
llo dis4[100001];
llo fin;
llo dp3[100001];
llo dp4[100001];
llo dp(llo no){
	llo mi=fin;
	llo ma=dis3[no];
	for(auto j:adj3[no]){
		if(dp3[j.a]==-1){
			dp(j.a);
		}
		ma=min(ma,dp3[j.a]);
		mi=min(mi,dp3[j.a]+dis4[no]);
	}
	fin=min(fin,mi);
	dp3[no]=ma;
	return ma;
}
llo dp2(llo no){
	llo mi=fin;
	llo ma=dis4[no];
	for(auto j:adj3[no]){
		if(dp4[j.a]==-1){
			dp2(j.a);
		}
		ma=min(ma,dp4[j.a]);
		mi=min(mi,dp4[j.a]+dis3[no]);
	}
	fin=min(fin,mi);
	dp4[no]=ma;
	return ma;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	memset(dp3,-1,sizeof(dp3));
	memset(dp4,-1,sizeof(dp4));
	llo n,m,s,t,u,v;
	cin>>n>>m;
	cin>>s>>t;
	cin>>u>>v;
	s-=1;
	t-=1;
	u-=1;
	v-=1;
	llo aa,bb,cc;
	for(llo i=0;i<m;i++){
		cin>>aa>>bb>>cc;
		adj[aa-1].pb(mp(bb-1,cc));
		adj[bb-1].pb({aa-1,cc});
	}
	llo dis[n];
	memset(dis,-1,sizeof(dis));
	dis[s]=0;

	priority_queue<pair<llo,llo>> pp;
	pp.push({0,s});
	while(!pp.empty()){
		pair<llo,llo> no=pp.top();
		pp.pop();
		no.a=-no.a;
		
		for(auto nn:adj[no.b]){
			if(dis[nn.a]==-1 or no.a+nn.b<dis[nn.a]){
				dis[nn.a]=no.a+nn.b;
				pp.push(mp(-dis[nn.a],nn.a));
			}
		}
	}
//	cout<<dis[t]<<endl;
	llo dis2[n];
	memset(dis2,-1,sizeof(dis2));
	dis2[t]=0;
	pp.empty();
	pp.push({0,t});
	while(!pp.empty()){
		pair<llo,llo> no=pp.top();
		pp.pop();
		no.a=-no.a;
		for(auto nn:adj[no.b]){
			if(dis2[nn.a]==-1 or no.a+nn.b<dis2[nn.a]){
				dis2[nn.a]=no.a+nn.b;
				pp.push(mp(-dis2[nn.a],nn.a));
			}
		}
	}
	for(llo i=0;i<n;i++){
		for(auto j:adj[i]){
			if(dis[i]+dis2[j.a]+j.b==dis[t]){
		    // 	cout<<i<<" "<<j.a<<endl;
			//	adj2[i].pb({j.a,j.b});
				adj3[j.a].pb({i,j.b});
			}
		}
	}
	memset(dis3,-1,sizeof(dis3));
	dis3[u]=0;
	pp.empty();
	pp.push({0,u});
	while(!pp.empty()){
		pair<llo,llo> no=pp.top();
		pp.pop();
		no.a=-no.a;
	
		for(auto nn:adj[no.b]){
			
			if(dis3[nn.a]==-1 or no.a+nn.b<dis3[nn.a]){
				dis3[nn.a]=no.a+nn.b;
				pp.push(mp(-dis3[nn.a],nn.a));
			}
		}
	}
	memset(dis4,-1,sizeof(dis4));
	dis4[v]=0;
	pp.empty();
	pp.push({0,v});
	while(!pp.empty()){
		pair<llo,llo> no=pp.top();
		pp.pop();
		no.a=-no.a;

		for(auto nn:adj[no.b]){
			
			if(dis4[nn.a]==-1 or no.a+nn.b<dis4[nn.a]){
				dis4[nn.a]=no.a+nn.b;
				pp.push(mp(-dis4[nn.a],nn.a));
			}
		}
	}
	fin=dis3[v];
//	cout<<fin<<endl;
	dp(t);
	dp2(t);
//	dp3(s);
//	dp4(s);
	cout<<fin<<endl;





	return 0;
}

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