Submission #651422

#	Time	Username	Problem	Language	Result	Execution time	Memory
651422		beaconmc	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	639 ms	41656 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];
vector<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 (sdists[i[0]] == sdists[a] - i[1]){
			newedges[i[0]].push_back(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] = 1000000000000000;
		udists[i] = 1000000000000000;
		vdists[i] = 1000000000000000;
	}


	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({s, 0});

	while (pq.size()){
		vector<ll> node = pq.top();
		pq.pop();
		if (node[1] != sdists[node[0]]) continue;
		for (auto&i : edges[node[0]]){
			if (!visited[i[0]] && sdists[i[0]] > sdists[node[0]] + i[1]){
				visited[i[0]] = true;
				sdists[i[0]] = sdists[node[0]] + i[1];
				pq.push({i[0], sdists[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({u, 0});


	while (pq.size()){
		vector<ll> node = pq.top();
		pq.pop();
		if (node[1] != udists[node[0]]) continue;
		for (auto&i : edges[node[0]]){
			if (!visited[i[0]] && udists[i[0]] > udists[node[0]] + i[1]){
				visited[i[0]] = true;
				udists[i[0]] = udists[node[0]] + i[1];
				pq.push({i[0], udists[i[0]]});
			}
		}
	}

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

	while (pq.size()){
		vector<ll> node = pq.top();
		pq.pop();
		if (node[1] != vdists[node[0]]) continue;
		for (auto&i : edges[node[0]]){
			if (!visited[i[0]] && vdists[i[0]] > vdists[node[0]] + i[1]){
				visited[i[0]] = true;
				vdists[i[0]] = vdists[node[0]] + i[1];
				pq.push({i[0], vdists[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 = 1000000000000000;

	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]);
		}
	}
	ans = min(ans, vdists[u]);
	cout << ans << endl;






}

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