제출 #1246488

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246488		nikulid	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	284 ms	25112 KiB

commuter_pass

/*
	this question is BFS final bos :sob:
*/

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool debug=0;
#define dout if(debug)cout

#define ll long long
#define pb push_back
#define mp make_pair

ll min_dist=1e18;
vector<ll> distS, distT, distU, distV;
vector<ll> mdistU, mdistV;
vector<vector<ll>> below;

ll minDU(int n){
	// 	what is the shortest distance between U and some node on some free path from S to `n`?
	// 	a.k.a.
	// 	with the option of using the free path, what is the smallest cost to get from U to `n`?
	if(mdistU[n] != -1){
		return mdistU[n];
	}
	ll answer=distU[n];
	for(int e:below[n]){
		answer = min(answer, minDU(e));
	}
	return mdistU[n]=answer;
}
ll minDV(int n){
	// 	what is the shortest distance between V and some node on some free path from S to `n`?
	if(mdistV[n] != -1){
		return mdistV[n];
	}
	ll answer=distV[n];
	for(int e:below[n]){
		answer = min(answer, minDV(e));
	}
	return mdistV[n]=answer;
}

int main(){
	
	// input
	ll n,m, s,t, u,v;
	cin>>n>>m;
	cin>>s>>t;
	cin>>u>>v;
	s--;t--;u--;v--;
	ll a,b,c;
	vector<vector<pair<ll, ll>>> adj(n);
	for(int i=0; i<m; i++){
		cin>>a>>b>>c;
		a--;b--;
		adj[a].pb(mp(b,c));
		adj[b].pb(mp(a,c));
	}
	
	mdistU = vector<ll>(n, -1);
	mdistV = vector<ll>(n, -1);
	// bfs to initialise distances from S/T/U/V to each node
	priority_queue<pair<ll, ll>> q;
	ll cur_dist, node;

	distS = vector<ll>(n, -1);
	q.push(mp(0, s));
	while(!q.empty()){
		cur_dist = q.top().first*-1;
		node = q.top().second;
		q.pop();
		if(distS[node] != -1)continue;
		distS[node] = cur_dist; // guaranteed minimum.
		for(int i=0; i<adj[node].size(); i++){
			if(distS[adj[node][i].first]==-1){
				q.push(mp(-1 * (cur_dist+adj[node][i].second), adj[node][i].first));
			}
		}
	}
	distT = vector<ll>(n, -1);
	q.push(mp(0, t));
	while(!q.empty()){
		cur_dist = q.top().first*-1;
		node = q.top().second;
		q.pop();
		if(distT[node] != -1)continue;
		distT[node] = cur_dist;
		for(int i=0; i<adj[node].size(); i++){
			if(distT[adj[node][i].first]==-1){
				q.push(mp(-1 * (cur_dist+adj[node][i].second), adj[node][i].first));
			}
		}
	}
	distU = vector<ll>(n, -1);
	q.push(mp(0, u));
	while(!q.empty()){
		cur_dist = q.top().first*-1;
		node = q.top().second;
		q.pop();
		if(distU[node] != -1)continue;
		distU[node] = cur_dist;
		for(int i=0; i<adj[node].size(); i++){
			if(distU[adj[node][i].first]==-1){
				q.push(mp(-1 * (cur_dist+adj[node][i].second), adj[node][i].first));
			}
		}
	}	
	distV = vector<ll>(n, -1);
	q.push(mp(0, v));
	while(!q.empty()){
		cur_dist = q.top().first*-1;
		node = q.top().second;
		q.pop();
		if(distV[node] != -1)continue;
		distV[node] = cur_dist;
		for(int i=0; i<adj[node].size(); i++){
			if(distV[adj[node][i].first]==-1){
				q.push(mp(-1 * (cur_dist+adj[node][i].second), adj[node][i].first));
			}
		}
	}

	// find the shortest distance by finding the minimum value of distS[i]+distT[i]
	for(int i=0; i<n; i++){
		min_dist = min(min_dist, distS[i]+distT[i]);
	}

	if(debug)
	{
		cout<<"shortest dist: "<<min_dist<<"\n";
		cout<<"debug distS: ";
		for(int i=0; i<n; i++){
			cout<<distS[i]<<" ";
		}cout<<"\n";
	}

	int e,cost;
	// compute `below` (directed graph of shortest paths from T to S)
	vector<int> onpath;
	below = vector<vector<ll>>(n);
	for(int i=0; i<n; i++){
		if(distS[i]+distT[i] == min_dist){ // node `i` lies on a path
			onpath.pb(i);
			for(int j=0; j<adj[i].size(); j++){
				e = adj[i][j].first;
				cost = adj[i][j].second;
				if(distS[e]+distT[e] == min_dist && distS[i]-cost == distS[e]){
					below[i].pb(e);
				}
			}
		}
	}


	// find minimum distance from U to V without considering the bridge between S and T
	ll minUV = 1e18;
	for(int i=0; i<n; i++){
		minUV = min(minUV, distU[i]+distV[i]);
	}	
	ll answer = minUV;

	ll node1;
	for(int i=0; i<onpath.size(); i++){
		node1 = onpath[i];
		answer = min(answer, minDU(node1)+distV[node1]);
		answer = min(answer, minDV(node1)+distU[node1]);
		minDU(node1);

	}

	cout<<answer<<"\n";
	return 0;
}

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