Submission #1042295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042295		beaconmc	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	577 ms	47872 KiB

commuter_pass

#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;


const ll INF = 10000000000000000;
vector<vector<ll>> edges[100005];
ll dp1[2][100005];
ll dp2[2][100005];
ll distss[100005];
ll distst[100005];
ll distsu[100005];
ll distsv[100005];



int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	FOR(i,0,2) FOR(j,0,100005) dp1[i][j] = INF, dp2[i][j] = INF;
	FOR(i,0,100005) distss[i]=INF,distst[i]=INF,distsu[i]=INF,distsv[i]=INF;


	ll n,m,s,t,u,v;
	cin >> n >> m;
	cin >> s >> t;
	cin >> u >> v;
	FOR(i,0,m){
		ll a,b,c;
		cin >> a >> b>> c;
		edges[a].push_back({b,c});
		edges[b].push_back({a,c});
	}

	priority_queue<vector<ll>> sus;
	sus.push({0, u});
	distsu[u] = 0;
	while (sus.size()){
		vector<ll> node = sus.top();
		sus.pop();
		node[0] = -node[0];
		if (distsu[node[1]] != node[0]) continue;
		for (auto&i : edges[node[1]]){
			if (distsu[i[0]] > i[1] + distsu[node[1]]){
				distsu[i[0]] = i[1] + distsu[node[1]];
				sus.push({-distsu[i[0]], i[0]});
			} 
		}
	}
	sus.push({0, v});
	distsv[v] = 0;
	while (sus.size()){
		vector<ll> node = sus.top();
		sus.pop();
		node[0] = -node[0];
		if (distsv[node[1]] != node[0]) continue;
		for (auto&i : edges[node[1]]){
			if (distsv[i[0]] > i[1] + distsv[node[1]]){
				distsv[i[0]] = i[1] + distsv[node[1]];
				sus.push({-distsv[i[0]], i[0]});
			} 
		}
	}
	FOR(i,1,n+1){
		dp1[0][i] = distsu[i];
		dp1[1][i] = distsv[i];
		dp2[0][i] = distsu[i];
		dp2[1][i] = distsv[i];
	}
	sus.push({0, s});
	distss[s] = 0;
	while (sus.size()){
		vector<ll> node = sus.top();
		sus.pop();
		node[0] = -node[0];
		if (distss[node[1]] != node[0]) continue;
		for (auto&i : edges[node[1]]){
			if (distss[i[0]] > i[1] + distss[node[1]]){
				distss[i[0]] = i[1] + distss[node[1]];
				sus.push({-distss[i[0]], i[0]});
			} 
		}
	}
	sus.push({0, t});
	distst[t] = 0;
	while (sus.size()){
		vector<ll> node = sus.top();
		sus.pop();
		node[0] = -node[0];
		if (distst[node[1]] != node[0]) continue;
		for (auto&i : edges[node[1]]){
			if (distst[i[0]] > i[1] + distst[node[1]]){
				distst[i[0]] = i[1] + distst[node[1]];
				sus.push({-distst[i[0]], i[0]});
			} 
		}
	}
	set<ll> visited;

	sus.push({0, s, distsu[s], distsv[s]});
	distss[s] = 0;
	dp1[0][s] = distsu[s];
	dp1[1][s] = distsv[s];
	visited.insert(s);
	while (sus.size()){
		vector<ll> node = sus.top();
		sus.pop();
		node[0] = -node[0];
		if (distss[node[1]] != node[0]) continue;
		for (auto&i : edges[node[1]]){
			if (distss[i[0]] == i[1] + distss[node[1]] && visited.count(i[0])==0){
				visited.insert(i[0]);
				distss[i[0]] = i[1] + distss[node[1]];
				sus.push({-distss[i[0]], i[0]});
				dp1[0][i[0]] = min(dp1[0][i[0]], dp1[0][node[1]]);
				dp1[1][i[0]] = min(dp1[1][i[0]], dp1[1][node[1]]);
			} else if (distss[i[0]] == i[1] + distss[node[1]]){
				dp1[0][i[0]] = min(dp1[0][i[0]], dp1[0][node[1]]);
				dp1[1][i[0]] = min(dp1[1][i[0]], dp1[1][node[1]]);
			}
		}
	}
	visited.clear();

	sus.push({0, t});
	distst[t] = 0;
	dp2[0][t] = distsu[t];
	dp2[1][t] = distsv[t];
	visited.insert(t);

	while (sus.size()){
		vector<ll> node = sus.top();

		sus.pop();
		node[0] = -node[0];
		if (distst[node[1]] != node[0]){
			continue;
		}
		for (auto&i : edges[node[1]]){
			if (distst[i[0]] == i[1] + distst[node[1]] && visited.count(i[0])==0){
				visited.insert(i[0]);
				distst[i[0]] = i[1] + distst[node[1]];
				sus.push({-distst[i[0]], i[0]});
				dp2[0][i[0]] = min(dp2[0][i[0]], dp2[0][node[1]]);
				dp2[1][i[0]] = min(dp2[1][i[0]], dp2[1][node[1]]);
			} else if (distst[i[0]] == i[1] + distst[node[1]]){
				dp2[0][i[0]] = min(dp2[0][i[0]], dp2[0][node[1]]);
				dp2[1][i[0]] = min(dp2[1][i[0]], dp2[1][node[1]]);
			}
		}
	}
	ll opt = distss[t];

	ll ans = INF;

	FOR(i,1,n+1){
		if (distss[i] + distst[i] != opt) continue;

		ans = min(ans, dp1[0][i] + dp2[1][i]);
		ans = min(ans, dp1[1][i] + dp2[0][i]);
	}



	cout << min(ans, distsu[v]) << endl;







}

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