제출 #1256526

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

commuter_pass

/*
Podzadanie: S = U

Złożoność: O(M logN)

Dla każdego wierzchołka X rozważamy, jaki jest wynik.
Zakładamy, że X jest ostatnim wierzchołkiem ze ścieżki od U do V,
który leży na jakiejś najkrótszej ścieżce z S do T.

Z U do X docieramy za darmo, a z X do V kosztem odległość X od V.
Aby sprawdzić, czy X leży na jakiejś najkrótszej ścieżce z S do T,
sprawdzamy czy odległość S do X i odległość X do T sumują się do odległości S do T.
*/

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

ll N, M, S, T, U, V;

vector<vector<pll>> graph;

const ll oo = 1e18;

vector<ll> Dijkstra(ll st)
{
	priority_queue<pll, vector<pll>, greater<pll>> pq;
	vector<ll> dist(N + 1, oo);
	dist[st] = 0;
	pq.push({0, st});
	while (pq.size())
	{
		auto [d, v] = pq.top();
		pq.pop();
		if (d != dist[v])
			continue;
		for (auto [u, c] : graph[v])
		{
			if (d + c < dist[u])
			{
				dist[u] = d + c;
				pq.push({dist[u], u});
			}
		}
	}
	return dist;
}

void init()
{
	cin >> N >> M >> S >> T >> U >> V;
	graph.resize(N + 1);
	for (ll i = 1, a, b, c; i <= M; i++)
	{
		cin >> a >> b >> c;
		graph[a].push_back({b, c});
		graph[b].push_back({a, c});
	}
}


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	init();
	vector<ll> dist_from_S = Dijkstra(S);
	vector<ll> dist_from_T = Dijkstra(T);
	vector<ll> dist_from_V = Dijkstra(V);
	ll ans = oo;
	for (ll X = 1; X <= N; X++)
	{
		if (dist_from_S[X] + dist_from_T[X] == dist_from_S[T])
			ans = min(ans, dist_from_V[X]);
	}
	cout << ans << '\n';
}

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