2011 - Crocodile

En lugar de intentar recorrer desde nuestro nodo de partida hacia un extremo, consideremos partir de los extremos e intentar llegar a nuestro nodo de partida.

El cocodrilo intentará impedirnos tomar el mejor camino desde un extremo dado hacia cualquier otro nodo. ¿Cómo podemos usar este conocimiento para decidir el menor tiempo que tardaríamos en llegar a un nodo desde cualquier extremo?

Explicación

Digamos que queremos llegar a un nodo dado desde un extremo de nuestro grafo. El cocodrilo siempre bloqueará la mejor ruta hacia un extremo del grafo, lo que significa que tenemos que tomar la segunda mejor ruta hacia un extremo.

Manejar la toma de decisiones de cuál es la “mejor elección” en un vértice dado es difícil si implementamos un algoritmo de caminos más cortos directamente sobre nuestro grafo. Por eso, modelamos el problema de una forma ligeramente distinta: en lugar de considerar la mejor distancia desde nuestro nodo de partida hacia cada extremo, consideramos la mejor distancia desde cualquier extremo hacia nuestro nodo de partida.

Esto hace que manejar la toma de decisiones sea significativamente más fácil porque significa que solo podemos usar la segunda mejor distancia hacia cualquier nodo dado. Nuestro algoritmo entonces se convierte en un Dijkstra multi-fuente típico, excepto que insertamos en la cola de prioridad cada vez que la segunda mejor distancia mejora.

Implementación

Complejidad temporal: $\mathcal{O}(M\log{M})$

#include <bits/stdc++.h>
using namespace std;
 
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	vector<vector<array<int, 2>>> adj(n);
	for (int i = 0; i < m; i++) {
		adj[r[i][0]].push_back({r[i][1], l[i]});
		adj[r[i][1]].push_back({r[i][0], l[i]});
	}
 
	// 1e9 porque la respuesta está garantizada a ser menor que eso
	const array<int, 2> DEFAULT = {(int)1e9, (int)1e9};
	// dist[i] = {mejor distancia, segunda mejor distancia}
	vector<array<int, 2>> dist(n, DEFAULT);
	priority_queue<array<int, 2>> pq;
	for (int i = 0; i < k; i++) {
		pq.push({0, p[i]});
		dist[p[i]] = {0, 0};
	}
 
	while (!pq.empty()) {
		auto [time, at] = pq.top();
		pq.pop();
		time *= -1;  // deshacemos el truco de los números negativos
		if (dist[at][1] < time) { continue; }
		for (const auto [nxt, weight] : adj[at]) {
			if (time + weight < dist[nxt][0]) {
				if (dist[nxt][0] < dist[nxt][1]) { pq.push({-dist[nxt][0], nxt}); }
				dist[nxt][1] = dist[nxt][0];
				dist[nxt][0] = time + weight;
			} else if (time + weight < dist[nxt][1]) {
				dist[nxt][1] = time + weight;
				pq.push({-dist[nxt][1], nxt});
			}
		}
	}
 
	return dist[0][1];
}