Submission #1266712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266712		WH8	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	498 ms	30904 KiB

commuter_pass

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

#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define maxn 100005
#define maxc 1e15
#define iii tuple<int,int,int>
int n,m,s,t,u,v,d;
vector<vector<pair<int,int>>> al(maxn);
vector<int> ds(maxn,maxc),dt(maxn,maxc),du(maxn,maxc),dv(maxn,maxc);
vector<vector<int>> mem(maxn, vector<int>(3, maxc));

void dijkstra(int start, vector<int> & dist){
	dist[start]=0;
	priority_queue<pair<int,int>, vector<pair<int,int>>,greater<pair<int,int>>> pq;
	pq.push({0, start});
	while(!pq.empty()){
		auto [cd, x] = pq.top();pq.pop();
		//~ printf("cur dist %lld  x is %lld\n", cd, x);
		if(dist[x]<cd)continue;
		for(auto [to, cost]:al[x]){
			//~ printf("to %lld, cost %lld\n",to,cost);
			if(cd+cost<dist[to]){
				dist[to]=cd+cost;
				pq.push({cd+cost, to});
			}
		}
	}
}

signed main(){
	cin>>n>>m>>s>>t>>u>>v;
	for(int i=0;i<m;i++){
		int a,b,c;cin>>a>>b>>c;
		al[a].pb({b,c});
		al[b].pb({a,c});
	}
	dijkstra(s, ds);
	dijkstra(t, dt);
	assert(dt[s]==ds[t]);
	d=dt[s];
	
	priority_queue<iii, vector<iii>,greater<iii>> pq;
	
	
	pq.push({0, u, 0});
	mem[u][0]=0;
	//0 not started, 1 in midst of, 2 exited. 
	while(!pq.empty()){
		auto [cd, x, st]=pq.top();pq.pop();
		if(mem[x][st]<cd)continue;
		for(auto [to, cost]:al[x]){
			if ((ds[x]+cost+dt[to]==d)
			and st!=2){
				if(cd<mem[to][1]){
					mem[to][1]=cd;
					pq.push({cd, to, 1});
				}
			}
			int nst=(st==1?2:st);
			if(cd+cost<mem[to][nst]){
				mem[to][nst]=cd+cost;
				pq.push({cd+cost, to, nst});
			}
		}	
	}
	int ans=maxc;
	ans=min({ans, mem[v][0], mem[v][1],mem[v][2]});
	
	for(int i=1;i<=n;i++)mem[i][0]=mem[i][1]=mem[i][2]=maxc;
	pq.push({0, u, 0});
	mem[u][0]=0;
	//0 not started, 1 in midst of, 2 exited. 
	while(!pq.empty()){
		auto [cd, x, st]=pq.top();pq.pop();
		if(mem[x][st]<cd)continue;
		for(auto [to, cost]:al[x]){
			if ((ds[to]+cost+dt[x]==d)
			and st!=2){
				if(cd<mem[to][1]){
					mem[to][1]=cd;
					pq.push({cd, to, 1});
				}
			}
			int nst=(st==1?2:st);
			if(cd+cost<mem[to][nst]){
				mem[to][nst]=cd+cost;
				pq.push({cd+cost, to, nst});
			}
		}	
	}
	ans=min({ans, mem[v][0], mem[v][1],mem[v][2]});
	cout<<ans;
	//~ cout<<"distance from s:\n";
	//~ for(int i=1;i<=n;i++){
		//~ cout<<ds[i]<<" ";
	//~ }
	//~ cout<<endl;
	//~ cout<<"distance from t:\n";
	//~ for(int i=1;i<=n;i++){
		//~ cout<<dt[i]<<" ";
	//~ }
	//~ cout<<endl;
		
	//~ cout<<"\ndistance from s:\n";
	//~ for(int i=1;i<=n;i++){
		//~ cout<<i<<": "<<mem[i][0]<<" "<<mem[i][1]<<" "<<mem[i][2]<<endl;
	//~ }
	//~ cout<<endl;
}

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