Ruta más barata entre dos paradas
La misión
Problema
Un mapa de reparto tiene n paradas numeradas de 0 a n - 1 y carreteras de un solo sentido dadas como [u, v, cost], donde cada costo es cero o más. Devuelve el costo total más barato para ir de la parada src a la parada dst, o -1 si no se puede llegar a dst.
Ejemplos
Input: n = 5, roads = [[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 5], [3, 4, 3]], src = 0, dst = 4
Output: 7
Por qué: 0 a 2 a 1 a 3 a 4 cuesta 1 + 2 + 1 + 3, menos que la carretera directa a 1, que por sí sola ya cuesta 4
Input: n = 3, roads = [[0, 1, 2]], src = 0, dst = 2
Output: -1
Por qué: ninguna carretera entra a la parada 2
Input: n = 2, roads = [[0, 1, 5]], src = 1, dst = 1
Output: 0
Por qué: caso límite: la ruta ya está en su destino
Pistas
0 / 3
La búsqueda en anchura encuentra la menor cantidad de carreteras, no el total más barato. Con costos en las carreteras, ¿de qué parada puedes estar seguro primero?
La parada sin fijar con el menor costo conocido nunca puede volverse más barata, porque cualquier otra ruta hacia ella pasaría por una parada que ya cuesta al menos lo mismo. Fija esa parada y actualiza sus vecinas.
Mantén un min-heap de (costo hasta ahora, parada), empezando con (0, src). Saca la entrada más barata, sáltala si ya se conoce un costo menor para esa parada y devuelve su costo cuando la parada sea dst. Si no, inserta cada vecina cuyo costo mejore.
- Tiempo objetivo
- O((n + m) log n)
- Espacio objetivo
- O(n + m)
Restricciones
- stops are numbered 0 to n - 1
- roads are one-way
- every cost ≥ 0
Solución
El algoritmo de Dijkstra fija las paradas en orden de su costo más barato. Como ninguna carretera tiene costo negativo, a la parada que está en la cima del min-heap no se puede llegar de forma más barata después, así que la primera vez que se saca dst su costo es definitivo y la búsqueda puede terminar. Una parada puede insertarse varias veces a medida que se encuentran rutas más baratas, y las entradas más viejas y más caras se saltan cuando salen. Con m carreteras, el tiempo es O((n + m) log n) y el espacio es O(n + m).
import heapq
def cheapest_route(n, roads, src, dst):
graph = [[] for _ in range(n)]
for u, v, cost in roads:
graph[u].append((v, cost))
best = [float("inf")] * n
best[src] = 0
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if u == dst:
return d # the first pop of dst is final
if d > best[u]:
continue # an older, more expensive entry
for v, cost in graph[u]:
if d + cost < best[v]:
best[v] = d + cost
heapq.heappush(heap, (best[v], v))
return -1
print(cheapest_route(5, [[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 5], [3, 4, 3]], 0, 4)) # -> 7
print(cheapest_route(3, [[0, 1, 2]], 0, 2)) # -> -1
print(cheapest_route(2, [[0, 1, 5]], 1, 1)) # -> 0¿Lo que te frena es la idea y no el código? El algoritmo de Dijkstra lo explica.