Submission #1256555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256555		4QT0R	Commuter Pass (JOI18_commuter_pass)	C++17	24 / 100	145 ms	327680 KiB

commuter_pass

/*
Podzadanie: N <= 300

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

Zauważmy, że odpowiedź jest nie większa niż odległość U do V.

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).
Od razu sprawdźmy wynik dla pary (Y, X).

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], dist[U][Y] + dist[X][V]});
		}
	}
	cout << min(dist[U][V], ans) << '\n';
}

/*
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1
*/

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