Saltar al contenido

Ruta más barata entre dos paradas

Fácil#dijkstra#min-heap~20 min

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

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

¿Lo que te frena es la idea y no el código? El algoritmo de Dijkstra lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio