Submission #1256508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256508		4QT0R	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	2092 ms	39816 KiB

commuter_pass

/*
Autor: Michał Kaźmierczak

Złożoność: O(W * M logN)
Gdzie W to liczba najkrótszych ścieżek z S do T. (W może być większe niż 2^{N/2})

Rozważamy wszystkie najktótsze ścieżki DFS-em.
Dijkstra z S wyznacza nam porządek częściowy związany z odległościami od S (DAG),
więc DFS się nie zacykli.
Korzystamy z F&U z cofaniem ostatnich zmian.
Rozważając pewną najkrótszą ścieżkę z S do T wykonaliśmy Union na wszystkich jej wierzchołkach.
Następnie puszczamy Dijkstrę z U, a wagi krawędzi w tej samej spójnej (tych na ścieżce) będziemy
traktować jak 0.
Bierzemy minimum z wszystkich wyników.
*/

#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;
vector<ll> lider;
vector<ll> siz;

stack<pll> changes;

vector<vector<ll>> dag;

const ll oo = 1e18;

ll Find(ll v)
{
	if (lider[v] == v)
		return v;
	changes.push({v, lider[v]});
	return lider[v] = Find(lider[v]);
}

void Union(ll a, ll b)
{
	a = Find(a);
	b = Find(b);
	if (a == b)
		return;
	if (siz[a] < siz[b])
		swap(a, b);
	changes.push({b, b});
	lider[b] = a;
	siz[a] += siz[b];
}

void Rollback()
{
	auto [v, p] = changes.top();
	changes.pop();
	if (v == p)
		siz[lider[v]] -= siz[v];
	lider[v] = p;
}

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 (Find(v) == Find(u))
				c = 0;
			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);
	dag.resize(N + 1);
	siz.resize(N + 1, 1);
	lider.resize(N + 1);
	iota(lider.begin(), lider.end(), 0);
	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});
	}
}

ll ans = oo;

void dfs(ll v)
{
	ll t = changes.size();
	if (v == T)
		ans = min(ans, Dijkstra(U)[V]);

	for (auto u : dag[v])
	{
		Union(v, u);
		dfs(u);
		while ((ll)changes.size() > t)
			Rollback();
	}
}

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

	init();
	vector<ll> dist = Dijkstra(S);
	for (ll v = 1; v <= N; v++)
	{
		for (auto [u, c] : graph[v])
		{
			if (dist[v] + c == dist[u])
				dag[v].push_back(u);
		}
	}
	dfs(S);
	cout << ans << '\n';
}

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