Submission #687734

#	Time	Username	Problem	Language	Result	Execution time	Memory
687734		NK_	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	372 ms	39912 KiB

commuter_pass

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define mp make_pair
#define f first
#define s second

using ll = long long;
using pi = pair<int, int>;
using C = array<ll, 2>;

template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;

const ll INFL = ll(1e18) + 10;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	

	int N, M; cin >> N >> M;

	int S, T, U, V; cin >> S >> T >> U >> V; --S, --T, --U, --V;

	vector<vector<pi>> adj(N);
	for(int i = 0; i < M; i++) {
		int u, v, w; cin >> u >> v >> w; --u, --v;
		adj[u].push_back(mp(v, w));
		adj[v].push_back(mp(u, w));
	}


	const int TIMES = 3;
	vector<vector<ll>> dst(N, vector<ll>(TIMES, INFL));

	vector<vector<int>> chd(N), ADJ(N), RADJ(N);

	auto dijk = [&](int s, int t, bool CHD) {
		vector<int> vis(N, 0);
		dst[s][t] = 0;
		pq<C> q; q.push(C{dst[s][t], s});

		while(size(q) > 0) {
			auto [d, u] = q.top(); q.pop();
			// cout << d << " " << u << endl;

			if (vis[u]) continue;
			vis[u] = 1;

			for(const auto &e : adj[u]) {
				int v, w; tie(v, w) = e;
				// cout << v << " - " << w << endl;
				if (dst[v][t] > dst[u][t]+w) {
					dst[v][t] = dst[u][t] + w;
					q.push(C{dst[v][t], v});
					if (CHD) chd[v] = {};
				}

				if (CHD && dst[v][t] == dst[u][t]+w) chd[v].push_back(u);
			}
		}
	};

	dijk(S, 0, 1);
	dijk(U, 1, 0);
	dijk(V, 2, 0);

	function<void(int)> make = [&](int u) {
		for(const auto &v : chd[u]) {
			// cout << u << " " << v << nl;
			ADJ[u].push_back(v);
			RADJ[v].push_back(u);	
			make(v);
		}
		chd[u] = {};
	};

	make(T);

	vector<array<ll, 2>> dp(N, {INFL, INFL}), rdp(N, {INFL, INFL}); // 0 -> U and 1 -> V

	for(int i = 0; i < N; i++) dp[i] = {dst[i][1], dst[i][2]}, rdp[i] = {dst[i][1], dst[i][2]};

	for(int t = 0; t < 2; t++) {
		
		vector<int> in(N);
		for(int u = 0; u < N; u++) for(auto v : ADJ[u]) in[v]++;

		queue<int> q;
		for(int u = 0; u < N; u++) if (in[u] == 0) q.push(u);

		while(size(q) > 0) {
			int u = q.front(); q.pop();

			for(auto v : ADJ[u]) {
				dp[v][0] = min(dp[v][0], dp[u][0]);
				dp[v][1] = min(dp[v][1], dp[u][1]);
				if (--in[v] == 0) q.push(v);
			}
		}

		ADJ.swap(RADJ);
		dp.swap(rdp);
	}

	ll ans = INFL;
	for(int i = 0; i < N; i++) {
		ans = min(ans, dp[i][0] + rdp[i][1]);
		ans = min(ans, rdp[i][0] + dp[i][1]);
	}

	cout << ans << nl;

    return 0;
}

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