Submission #41167

#	Time	Username	Problem	Language	Result	Execution time	Memory
41167		sinhriv	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	629 ms	27312 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

const int NN = 200200;

int N, M;
int S, T, U, V;
int deg[NN];
long long fr[NN];
long long to[NN];
long long f[4][NN];
vector < int > dag[NN];
vector < pair < int, int > > e[NN];

bool minimize(long long &x, long long y){
	if(x > y){
		x = y;
		return true;
	}
	return false;
}

void Dijkstra(int start, long long *d){
	fill(d, d + N + 1, 1e18);
	d[start] = 0;

	vector < bool > done(N + 1, 0);
	set < pair < long long, int > > heap;
	heap.emplace(0, start);

	while(!heap.empty()){
		int x = heap.begin() -> second;
		heap.erase(heap.begin());


		if(done[x]) continue;
		done[x] = 1;

		for(auto c : e[x]){
			if(minimize(d[c.first], d[x] + c.second)){
				heap.emplace(d[c.first], c.first);
			}
		}
	}
}

int main(){

	scanf("%d%d%d%d%d%d", &N, &M, &S, &T, &U, &V);

	while(M--){
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		e[u].emplace_back(v, w);
		e[v].emplace_back(u, w);
	}


	Dijkstra(S, f[0]);
	Dijkstra(T, f[1]);
	Dijkstra(U, f[2]);
	Dijkstra(V, f[3]);

	long long ans = f[2][V];

	for(int x = 1; x <= N; ++x){
		for(auto c : e[x]){
			int y = c.first, w = c.second;

			if(f[0][x] + w == f[0][y]) dag[x].push_back(y), ++deg[y];
		}
	}

	vector < int > lst, perm;

	for(int i = 1; i <= N; ++i){
		if(deg[i] == 0) lst.push_back(i);
	}

	while(!lst.empty()){
		int x = lst.back();
		lst.pop_back();

		perm.push_back(x);

		for(int y : dag[x]){
			if(--deg[y] == 0) lst.push_back(y);
		}
	}

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


	for(int x : perm){

		fr[x] = to[x] = 1e18;

		if(f[0][x] + f[1][x] != f[0][T]) continue;

		fr[x] = f[2][x];
		to[x] = f[3][x];



		for(int y : dag[x]){
			fr[x] = min(fr[x], fr[y]);
			to[x] = min(to[x], to[y]);
		}


		ans = min(ans, f[3][x] + fr[x]);
		ans = min(ans, f[2][x] + to[x]);

	}


	cout << ans;

	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:50:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d%d%d", &N, &M, &S, &T, &U, &V);
                                               ^
commuter_pass.cpp:54:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &w);
                              ^

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