Submission #537872

#	Time	Username	Problem	Language	Result	Execution time	Memory
537872		tkwiatkowski	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	364 ms	21612 KiB

commuter_pass

/*
	Zadanie: Commuter Pass
	Autor: Tomasz Kwiatkowski
*/

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef long long ll;

const int MAXN = 1e5 + 7;
const int INF = 1e9 + 7;

vector<pair<int, int>> G[MAXN];
ll dist[4][MAXN];
ll dp[2][MAXN];
int n;

void Dijkstra(int start, ll* dist)
{
	for (int i = 1; i <= n; ++i)
		dist[i] = 1e18;

	priority_queue<pair<ll, int>> Q;
	Q.push({0, start});
	while (Q.size()) {
		auto [d, v] = Q.top();
		Q.pop();
		if (-d >= dist[v])
			continue;
		dist[v] = -d;
		for (auto [u, w] : G[v]) {
			if (dist[u] > dist[v] + w)
				Q.push({-(dist[v] + w), u});
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);

	int m;
	int S, T, U, V;
	cin >> n >> m;
	cin >> S >> T;
	cin >> U >> V;
	for (int i = 0; i < m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		G[u].pb({v, w});
		G[v].pb({u, w});
	}

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

	vector<pair<ll, int>> tmp;
	for (int v = 1; v <= n; ++v)
		tmp.pb({dist[0][v], v});
	sort(tmp.begin(), tmp.end());
	ll D = dist[0][T];
	for (auto [_, v] : tmp) {
		dp[0][v] = dist[2][v];
		dp[1][v] = dist[3][v];
		for (auto [u, w] : G[v]) {
			if (dist[0][u] + w == dist[0][v] && dist[0][v] + dist[1][v] == D) {
				dp[0][v] = min(dp[0][v], dp[0][u]);
				dp[1][v] = min(dp[1][v], dp[1][u]);
			}
		}
	}

	ll ans = dist[2][V];
	for (int v = 1; v <= n; ++v) {
		if (dist[0][v] + dist[1][v] != D)
			continue;
		ans = min({dp[0][v] + dist[3][v],
				   dp[1][v] + dist[2][v],
				   ans});
	}
	cout << ans << '\n';
	return 0;
}

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