Submission #687739

#	Time	Username	Problem	Language	Result	Execution time	Memory
687739		NK_	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	348 ms	36016 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>>;

int stk[123];
long long read() {
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		ch = getchar();
	}
	long long v = 0;
	while ('0' <= ch && ch <= '9') {
		v = v * 10 + (int) (ch - '0');
		ch = getchar();
	}
	return v;
}
 
void write(ll x) {
	int len = 0;
	while (x > 0) {
		stk[len++] = x % 10;
		x /= 10;
	}
	for (int i = len - 1; i >= 0; i--) {
		putchar('0' + stk[i]);
	}
 	if (len == 0) {
		putchar('0');
	}
	putchar('\n');
}

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

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

	int N = read(), M = read();

	int S = read()-1, T = read()-1, U = read()-1, V = read()-1;

	vector<vector<pi>> adj(N);
	for(int i = 0; i < M; i++) {
		int u = read()-1, v = read()-1, w = read();
		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) {
			int u = q.top()[1]; 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]);
	}

	write(ans);

    return 0;
}

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