제출 #1256540

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

commuter_pass

/*
Podzadanie: N <= 300

Złożoność: O(N^3)

Dla każdej pary wierzchołków X, Y rozważamy, jaki jest wynik.
Zakładamy, że X jest pierwszyn wierzchołkiem ze ścieżki od U do V,
który leży na jakiejś najkrótszej ścieżce z S do T, a Y ostatnim.
Zauważmy tutaj, że X oraz Y muszą być na tej samej ścieżce.
Oznacza to, że z X do Y możemy się dostać kosztem 0.

Oznaczmy d(v, u) odległość v oraz u.

Z U do X docieramy kosztem d(U, X), z X do Y kosztem 0, a z Y do V kosztem d(Y, V).
Aby sprawdzić, czy X, Y leżą na jakiejś najkrótszej ścieżce z S do T,
sprawdzamy czy d(S, X) + d(X, Y) + d(Y, T) = d(S, T).

Odległości między każdą parą wierzchołków liczymy algorytmem Floyda-Warshalla.
*/

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

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

vector<vector<ll>> dist;

const ll oo = 1e18;

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

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

	init();
	for (ll k = 1; k <= N; k++)
	{
		for (ll v = 1; v <= N; v++)
		{
			for (ll u = 1; u <= N; u++)
			{
				dist[v][u] = min({dist[v][u], dist[v][k] + dist[k][u]});
			}
		}
	}
	ll ans = oo;
	for (ll X = 1; X <= N; X++)
	{
		for (ll Y = 1; Y <= N; Y++)
		{
			if (dist[S][X] + dist[X][Y] + dist[Y][T] == dist[S][T])
				ans = min(ans, dist[U][X] + dist[Y][V]);
		}
	}
	cout << ans << '\n';
}

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