Skip to Content
CTRL K

Shortest Paths

Grafo general -> Árbol

Los grafos generales son incómodos: ¡intentemos convertir este grafo en un árbol!

Ejecutamos el algoritmo de Dijkstra desde el nodo AA hacia todos los demás nodos y construimos el “árbol de caminos más cortos” a partir de esto (es decir, el árbol formado por la unión de los caminos más cortos del nodo AA a cada uno de los demás nodos). ¡Hay que forzar que el camino de la suerte dado en la entrada esté en este árbol!

¿Por qué es esto útil? En este caso, obtenemos algunas propiedades interesantes al quitar aristas del camino de la suerte.

¿Qué pasa cuando quitamos una arista?

Cuando quitamos una arista del camino de la suerte, el árbol se parte en dos árboles más pequeños: uno que contiene AA; otro que contiene BB.

Esto significa que el camino más corto A→BA \rightarrow B debe ser de la forma A→u→v→BA \rightarrow u \rightarrow v \rightarrow B donde uu y vv son dos nodos unidos por una arista y uu está en el árbol de AA mientras que vv está en el árbol de BB.

¿Por qué es esto cierto?

Primero, cualquier vértice sigue conectado o bien a AA a través de su árbol de caminos más cortos o bien a BB a través de su árbol de caminos más cortos después de quitar una sola arista del camino más corto.

Segundo, debemos “saltar” de un subárbol al otro en algún momento, así que los nuevos caminos más cortos deben tener dos nodos en subárboles separados unidos por una arista.

Actualizar los caminos más cortos

Una observación importante es que si seguimos subiendo de un nodo a su padre, eventualmente llegaremos a un nodo del camino de la suerte. Para el nodo vv, sea este nodo del camino de la suerte PvP_v. Como NN es tan pequeño, podemos hallar de forma naive PvP_v para cada vv.

Como uu y vv deben estar en subárboles separados, el camino A→u→v→BA \rightarrow u \rightarrow v \rightarrow B solo es candidato a camino más corto después de quitar una arista si esa arista está entre PuP_u y PvP_v.

Así, solo debemos actualizar los caminos más cortos después de quitar una arista para las aristas entre PuP_u y PvP_v para cada arista (u,v)(u, v).

De nuevo, podemos actualizar de forma naive estos caminos más cortos.

La complejidad final de este algoritmo es O(MN+Mlog⁡N)\mathcal{O}(MN + M \log N)

Implementación

Complejidad temporal: O(MN+Mlog⁡N)\mathcal{O}(MN + M \log N)

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
struct Edge {
	int u, v;
	ll c;
} edges[200000];
 
bool operator<(Edge a, Edge b) {
	if (a.c == b.c) {
		if (a.u == b.u) return a.v < b.v;
		return a.u < b.u;
	}
	return a.c < b.c;
}
 
vector<pair<int, ll>> graph[2001];
vector<int> sp_tree[2001];
int sp[2001], lca[2001];
ll from_a[2001], from_b[2001], ans[2001];
int par[2001], depth[2001];
 
void dijkstra(int source, ll *dist) {
	priority_queue<tuple<ll, int, int>> pq;
	pq.push({-1, source, 0});
	while (pq.size()) {
		int curr, parent;
		ll cost;
		tie(cost, curr, parent) = pq.top();
		pq.pop();
		if (!dist[curr]) {
			par[curr] = parent;
			dist[curr] = -cost;
			for (pair<int, ll> i : graph[curr])
				pq.push({cost - i.second, i.first, curr});
		}
	}
}
 
void dfs(int node) {
	for (int i : sp_tree[node]) {
		depth[i] = depth[node] + 1;
		dfs(i);
	}
}
 
int find_lca(int a, int b) {
	while (depth[a] > depth[b]) a = par[b];
	while (depth[b] > depth[a]) b = par[b];
	while (a != b) a = par[a], b = par[b];
	return a;
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m, a, b, k;
	cin >> n >> m >> a >> b;
	for (int i = 0; i < m; i++) {
		cin >> edges[i].u >> edges[i].v >> edges[i].c;
		edges[i + m] = {edges[i].v, edges[i].u, edges[i].c};
		graph[edges[i].u].push_back({edges[i].v, edges[i].c});
		graph[edges[i].v].push_back({edges[i].u, edges[i].c});
	}
 
	dijkstra(b, from_b);
	dijkstra(a, from_a);
 
	cin >> k;
	for (int i = 0; i < k; i++) {
		cin >> sp[i];
		if (i) par[sp[i]] = sp[i - 1];
	}
 
	for (int i = 1; i <= n; i++)
		if (par[i]) sp_tree[par[i]].push_back(i);
	dfs(a);
	for (int i = 1; i <= n; i++) lca[i] = find_lca(i, b);
 
	memset(ans, 0x3f, sizeof(ans));
	for (int i = 0; i < 2 * m; i++) {
		if (par[edges[i].u] == edges[i].v || par[edges[i].v] == edges[i].u) continue;
		int x = find(sp, sp + k, lca[edges[i].u]) - sp;
		int y = find(sp, sp + k, lca[edges[i].v]) - sp;
		for (int j = x; j < y; j++)
			ans[j] =
			    min(ans[j], from_a[edges[i].u] + from_b[edges[i].v] + edges[i].c - 2);
	}
 
	for (int i = 0; i < k - 1; i++)
		cout << (ans[i] == 0x3f3f3f3f3f3f3f3f ? -1 : ans[i]) << '\n';
	return 0;
}
Fundamentos