제출 #976390

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
976390		LmaoLmao	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	399 ms	29736 KiB

commuter_pass

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;

using ll = long long;
using ii = pair<ll, ll>;
using aa= array<ll,3>; 

const int N = 1e6+5;
const int INF = 1e9;

ll sr[100001][2];
ll d[100001][2]; 
ll D[100001][2]; 
vector<ii> adj[100001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,m,s,t,u,v;
	cin >> n >> m;
	cin >> s >> t;
	cin >> u >> v;
	for(int i=0;i<m;i++) {
		ll a,b,c;
		cin >> a >> b >> c;
		adj[a].push_back({b,c});
		adj[b].push_back({a,c});
	}
	for(int i=1;i<=n;i++) {
		d[i][0]=(ll)1e15;
		d[i][1]=(ll)1e15;
		D[i][0]=(ll)1e15;
		D[i][1]=(ll)1e15;
		sr[i][0]=(ll)1e15;
		sr[i][1]=(ll)1e15;
	}
	priority_queue<aa,vector<aa>,greater<aa>> q;
	q.push({0,s,0});
	q.push({0,t,1});
	sr[s][0]=0;
	sr[t][1]=0;
	while(!q.empty()) {
		aa cur=q.top();
		q.pop();
		if(cur[0]>sr[cur[1]][cur[2]]) continue;
		for(ii to:adj[cur[1]]) {
			if(sr[to.fi][cur[2]]>sr[cur[1]][cur[2]]+to.se) {
				sr[to.fi][cur[2]]=sr[cur[1]][cur[2]]+to.se;
				q.push({sr[to.fi][cur[2]],to.fi,cur[2]});	
			}
		}
	}
	q.push({0,u,0});
	ll l=sr[t][0];
	d[u][0]=0;
	while(!q.empty()) {
		aa cur=q.top();
		q.pop();
		if(cur[0]>d[cur[1]][cur[2]]) continue;
		if(sr[cur[1]][0]+sr[cur[1]][1]==l && cur[2]==0) {
			queue<int> bfs;
			if(d[cur[1]][1]>d[cur[1]][0]) {
				d[cur[1]][1]=d[cur[1]][0];
				q.push({d[cur[1]][1],cur[1],1});
			}
			for(ii to:adj[cur[1]]) {
				if(sr[to.fi][0]+to.se==sr[cur[1]][0] && d[to.fi][1]>cur[0]) {
					d[to.fi][1]=cur[0];
					bfs.push(to.fi);
					q.push({d[to.fi][1],to.fi,1}); 
				}
			}
			while(!bfs.empty()) {
				int k=bfs.front();
				bfs.pop();
				for(ii to:adj[k]) {
					if(sr[to.fi][0]+to.se==sr[k][0] && d[to.fi][1]>d[k][1]) {
						d[to.fi][1]=d[k][1];
						bfs.push(to.fi);
						q.push({d[to.fi][1],to.fi,1}); 
					}
				}
			}
			for(ii to:adj[cur[1]]) {
				if(sr[to.fi][1]+to.se==sr[cur[1]][1] && d[to.fi][1]>cur[0]) {
					d[to.fi][1]=cur[0];
					bfs.push(to.fi);
					q.push({d[to.fi][1],to.fi,1}); 
				}
			}
			while(!bfs.empty()) {
				int k=bfs.front();
				bfs.pop();
				for(ii to:adj[k]) {
					if(sr[to.fi][1]+to.se==sr[k][1] && d[to.fi][1]>d[k][1]) {
						d[to.fi][1]=d[k][1];
						bfs.push(to.fi);
						q.push({d[to.fi][1],to.fi,1}); 
					}
				}
			}
		}
		for(ii to:adj[cur[1]]) {
			if(d[to.fi][cur[2]]>d[cur[1]][cur[2]]+to.se) {
				d[to.fi][cur[2]]=d[cur[1]][cur[2]]+to.se;
				q.push({d[to.fi][cur[2]],to.fi,cur[2]});	
			}
		}
	}
	q.push({0,v,0});
	D[v][0]=0;
	while(!q.empty()) {
		aa cur=q.top();
		q.pop();
		if(cur[0]>D[cur[1]][cur[2]]) continue;
		if(sr[cur[1]][0]+sr[cur[1]][1]==l && cur[2]==0) {
			queue<int> bfs;
			if(D[cur[1]][1]>D[cur[1]][0]) {
				D[cur[1]][1]=D[cur[1]][0];
				q.push({D[cur[1]][1],cur[1],1});
			}
			for(ii to:adj[cur[1]]) {
				if(sr[to.fi][0]+to.se==sr[cur[1]][0] && D[to.fi][1]>cur[0]) {
					D[to.fi][1]=cur[0];
					bfs.push(to.fi);
					q.push({D[to.fi][1],to.fi,1}); 
				}
			}
			while(!bfs.empty()) {
				int k=bfs.front();
				bfs.pop();
				for(ii to:adj[k]) {
					if(sr[to.fi][0]+to.se==sr[k][0] && D[to.fi][1]>D[k][1]) {
						D[to.fi][1]=D[k][1];
						bfs.push(to.fi);
						q.push({D[to.fi][1],to.fi,1}); 
					}
				}
			}
			for(ii to:adj[cur[1]]) {
				if(sr[to.fi][1]+to.se==sr[cur[1]][1] && D[to.fi][1]>cur[0]) {
					D[to.fi][1]=cur[0];
					bfs.push(to.fi);
					q.push({D[to.fi][1],to.fi,1}); 
				}
			}
			while(!bfs.empty()) {
				int k=bfs.front();
				bfs.pop();
				for(ii to:adj[k]) {
					if(sr[to.fi][1]+to.se==sr[k][1] && D[to.fi][1]>D[k][1]) {
						D[to.fi][1]=D[k][1];
						bfs.push(to.fi);
						q.push({D[to.fi][1],to.fi,1}); 
					}
				}
			}
		}
		for(ii to:adj[cur[1]]) {
			if(D[to.fi][cur[2]]>D[cur[1]][cur[2]]+to.se) {
				D[to.fi][cur[2]]=D[cur[1]][cur[2]]+to.se;
				q.push({D[to.fi][cur[2]],to.fi,cur[2]});	
			}
		}
	}
	cout << min(min(d[v][1],d[v][0]),min(D[u][1],D[u][0]));
    return 0;
}

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