Submission #651460

#	Time	Username	Problem	Language	Result	Execution time	Memory
651460		beaconmc	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	800 ms	63072 KiB

commuter_pass

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

vector<vector<ll>> edges[100001];
unordered_set<ll> newedges[100001];
ll sdists[100001];
ll udists[100001];
ll vdists[100001];
ll visited[100001];
ll dp[2][100001];

vector<ll> topsort;

void dfs(ll a){
	for (auto&i : edges[a]){
		if (newedges[i[0]].count(a)) continue;

		if (sdists[i[0]] == sdists[a] - i[1]){
			newedges[i[0]].insert(a);
			dfs(i[0]);
		}
	}
}

void dfs2(ll a){
	for (auto&i : newedges[a]){
		if (!visited[i]){
			visited[i] = true;
			dfs2(i);
		}
	}
	topsort.push_back(a);
}

int main(){
	ll n,m,s,t,u,v;
	cin >> n >> m >> s >> t >> u >> v;



	FOR(i,0,100001){
		sdists[i] = LLONG_MAX / 2;
		udists[i] = LLONG_MAX / 2;
		vdists[i] = LLONG_MAX / 2;
	}


	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>, vector<vector<ll>>, greater<vector<ll>>> pq;

	FOR(i,0,100001) visited[i] = false;
	visited[s] = true;
	sdists[s] = 0;
	pq.push({0,s});


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

		if (node[0] != sdists[node[1]]) continue;
		for (auto&i : edges[node[1]]){
			if (sdists[i[0]] > sdists[node[1]] + i[1]){
				sdists[i[0]] = sdists[node[1]] + i[1];
				pq.push({sdists[i[0]],i[0]});
			}
		}
	}




	FOR(i,0,100001) visited[i] = false;
	visited[t] = true;
	dfs(t);


	FOR(i,0,100001) visited[i] = false;
	visited[u] = true;
	udists[u] = 0;
	pq.push({0,u});


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

		if (node[0] != udists[node[1]]) continue;
		for (auto&i : edges[node[1]]){
			if (udists[i[0]] > udists[node[1]] + i[1]){

				udists[i[0]] = udists[node[1]] + i[1];
				pq.push({udists[i[0]],i[0]});
			}
		}
	}

	FOR(i,0,100001) visited[i] = false;
	visited[v] = true;
	vdists[v] = 0;
	pq.push({0,v});

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


		pq.pop();
		if (node[0] != vdists[node[1]]) continue;
		for (auto&i : edges[node[1]]){
			if (vdists[i[0]] > vdists[node[1]] + i[1]){

				vdists[i[0]] = vdists[node[1]] + i[1];

				pq.push({vdists[i[0]],i[0]});
			}
		}
	}



	FOR(i,0,100001) visited[i] = false;
	FOR(i,1,n+1){
		if (!visited[i] && newedges[i].size()){
			visited[i] = true;
			dfs2(i);
		}
	}

	FOR(i,0,100001){
		dp[0][i] = udists[i];
		dp[1][i] = vdists[i];
	}


	reverse(topsort.begin(), topsort.end());



	ll ans = LLONG_MAX / 2;

	for (auto&i : topsort){
		//cout << i << " " << dp[1][i] << " " << dp[0][i] << endl;

		ans = min(ans, dp[1][i] + dp[0][i]);

		for (auto&j : newedges[i]){

			dp[1][j] = min(dp[1][j], dp[1][i]);
			ans = min(ans, dp[1][j] + dp[0][j]);
		}
	}

	FOR(i,0,100001){
		dp[0][i] = udists[i];
		dp[1][i] = vdists[i];
	}
	for (auto&i : topsort){
		//cout << i << " " << dp[1][i] << " " << dp[0][i] << endl;

		ans = min(ans, dp[1][i] + dp[0][i]);

		for (auto&j : newedges[i]){
			dp[0][j] = min(dp[0][j], dp[0][i]);

			ans = min(ans, dp[1][j] + dp[0][j]);
		}
	}

	ans = min(ans, vdists[u]);


	cout << ans << endl;







}

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