Submission #854436

#	Time	Username	Problem	Language	Result	Execution time	Memory
854436		QuangBui	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	311 ms	25296 KiB

commuter_pass

// QuangBuiCP
// 375.cpp
#include "bits/stdc++.h"
using namespace std;
#ifdef LOCAL
#include "local/debug.hpp"
#else
#define debug(...)
#endif // LOCAL

#define SZ(a) (int)(a).size()
#define ALL(a) (a).begin(),(a).end()

#define int long long

struct State {
	int x;
	int dist;
	bool operator < (const State& other) const {
		return dist > other.dist;
	}
};

vector<int> run_dijkstra(int n, const vector<vector<pair<int, int>>>& g, int start) {
	vector<int> dist(n, LLONG_MAX / 2);
	priority_queue<State> pq;
	pq.push({start, 0});
	dist[start] = 0;
	while (SZ(pq)) {
		State top = pq.top(); pq.pop();
		int u = top.x;
		int cur = top.dist;
		if (dist[u] != cur) {
			continue;
		}
		for (auto& p : g[u]) {
			int v = p.first;
			int w = p.second;
			if (cur + w < dist[v]) {
				dist[v] = cur + w;
				pq.push({v, dist[v]});
			}
		}
	}
	return dist;
}

signed main() {
#ifndef LOCAL
	cin.tie(nullptr)->sync_with_stdio(false);
#endif // LOCAL

	int n, m;
	cin >> n >> m;
	int S, T, X, Y;
	cin >> S >> T >> X >> Y; S--, T--, X--, Y--;
	vector<vector<pair<int, int>>> g(n);
	for (int i = 0; i < m; ++i) {
		int x, y, w;
		cin >> x >> y >> w; x--, y--;
		g[x].emplace_back(y, w);
		g[y].emplace_back(x, w);
	}
	vector<int> dS = run_dijkstra(n, g, S);
	vector<int> dT = run_dijkstra(n, g, T);
	vector<int> dX = run_dijkstra(n, g, X);
	vector<int> dY = run_dijkstra(n, g, Y);
	long long min_dist = dS[T];
	auto Calc = [&](const vector<int>& s, const vector<int>& t, const vector<int>& d, int start) {
		vector<int> topo;
		vector<bool> vis(n, false);
		function<void(int)> dfs = [&](int u) {
			vis[u] = true;
			for (auto& p : g[u]) {
				int v = p.first;
				int w = p.second;
				if (s[u] + w == min_dist - t[v] && !vis[v]) {
					dfs(v);
				}
			}
			topo.push_back(u);
		};
		dfs(start);
		reverse(ALL(topo));
		vector<int> dp(n, LLONG_MAX / 2);
		for (int u : topo) {
			dp[u] = min(dp[u], d[u]);
			for (auto& p : g[u]) {
				int v = p.first;
				int w = p.second;
				if (s[u] + w == min_dist - t[v]) {
					dp[v] = min(dp[v], dp[u]);
				}
			}
		}
		return dp;
	};
	vector<int> sx = Calc(dS, dT, dX, S);
	vector<int> sy = Calc(dS, dT, dY, S);
	vector<int> tx = Calc(dT, dS, dX, T);
	vector<int> ty = Calc(dT, dS, dY, T);
	int ans = dX[Y];
	for (int i = 0; i < n; ++i) {
		ans = min(ans, min(sx[i] + ty[i], sy[i] + tx[i]));
	}
	cout << ans << '\n';

#ifdef LOCAL
	cout << '\n' << clock() << "ms.";
#endif // LOCAL
	return 0;
}

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