제출 #1261953

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261953		4QT0R	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	2068 ms	327680 KiB

commuter_pass

/*
Zła Dijkstra
<= zamiast < przy relaksowaniu krawędzi
*/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>

vector<pii> graph[100003];
ll n, m, S, T, U, V, oo = 1e18 + 1, min_dist;
ll dist[4][100003];
ll wyn[2][100003];

void Dijkstra(ll st, ll par)
{
	fill(dist[par], dist[par] + n + 1, oo);
	dist[par][st] = 0;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({0, st});
	while (pq.size())
	{
		auto [d, v] = pq.top();
		pq.pop();
		for (auto [u, w] : graph[v])
		{
			if (d + w <= dist[par][u])
			{
				dist[par][u] = d + w;
				pq.push({d + w, u});
			}
		}
	}
}

ll dfs(ll v, ll par)
{
	if (wyn[par][v] < oo)
		return wyn[par][v];
	wyn[par][v] = dist[0][v];
	for (auto u : graph[v])
	{
		if (dist[par + 2][v] + u.second + dist[(par ^ 1) + 2][u.first] == min_dist)
		{
			wyn[par][v] = min(wyn[par][v], dfs(u.first, par));
		}
	}
	return wyn[par][v];
}

void init()
{
	cin >> n >> m >> S >> T >> U >> V;
	ll a, b, c;
	for (ll i = 1; i <= m; i++)
	{
		cin >> a >> b >> c;
		graph[a].push_back({b, c});
		graph[b].push_back({a, c});
	}
	Dijkstra(U, 0);
	Dijkstra(V, 1);
	Dijkstra(S, 2);
	Dijkstra(T, 3);
	min_dist = dist[2][T];
	fill(wyn[0], wyn[0] + n + 1, oo);
	fill(wyn[1], wyn[1] + n + 1, oo);
}

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

	init();
	ll ans = dist[0][V];
	for (ll i = 1; i <= n; i++)
	{
		if (dist[2][i] + dist[3][i] == min_dist)
			ans = min(ans, min(dfs(i, 0), dfs(i, 1)) + dist[1][i]);
	}
	cout << ans << '\n';
}

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