Submission #535142

#	Time	Username	Problem	Language	Result	Execution time	Memory
535142		amunduzbaev	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	452 ms	26444 KiB

commuter_pass

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

#define ar array
#define int long long

const int N = 1e5 + 5;
const int inf = 1e18;
vector<ar<int, 2>> edges[N];
int d[4][N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	vector<int> s(4);
	for(int i=0;i<4;i++) cin>>s[i];
	for(int i=0;i<m;i++){
		int a, b, c; cin>>a>>b>>c;
		edges[a].push_back({b, c});
		edges[b].push_back({a, c});
	}
	
	auto djk = [&](int u, int* d){
		d[u] = 0;
		priority_queue<ar<int, 2>, vector<ar<int, 2>>, greater<ar<int, 2>>> q;
		q.push({d[u], u});
		while(!q.empty()){
			int u = q.top()[1], D = q.top()[0]; q.pop();
			if(D > d[u]) continue;
			for(auto x : edges[u]){
				if(d[x[0]] > d[u] + x[1]){
					d[x[0]] = d[u] + x[1];
					q.push({d[x[0]], x[0]});
				}
			}
		}
	};
	
	memset(d, 63, sizeof d);
	for(int i=1;i<4;i++){
		djk(s[i], d[i]);
	}
	
	int res = d[2][s[3]];
	int TRU = d[1][s[0]];
	auto dj2 = [&](int a, int b){
		priority_queue<ar<int, 3>, vector<ar<int, 3>>, 	greater<ar<int, 3>>> q;
		vector<ar<int, 2>> _d(n + 1, {inf, inf});
		_d[s[0]] = {0, d[a][s[0]]};
		q.push({0, d[a][s[0]], s[0]});
		while(!q.empty()){
			int D = q.top()[0], _D = q.top()[1], u = q.top()[2]; q.pop();
			if(D > _d[u][0] || _D > _d[u][1]) continue;
			if(d[1][u] + D == TRU) res = min(res, _D + d[b][u]);
			//~ cout<<_D<<" "<<d[b][u]<<" "<<u<<"\n";
			for(auto x : edges[u]){
				if(_d[x[0]] > (ar<int, 2>){D + x[1], min(_D, d[a][x[0]])}){
					_d[x[0]] = {D + x[1], min(_D, d[a][x[0]])};
					q.push({_d[x[0]][0], _d[x[0]][1], x[0]});
				}
			}
		}
	};
	
	dj2(2, 3);
	dj2(3, 2);
	cout<<res<<"\n";
}

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