Saltar al contenido

Caminos más cortos con reembolsos

Fácil#bellman-ford#negative-edges~20 min

La misión

Problema

Una región tiene n pueblos numerados de 0 a n - 1 y carreteras de un solo sentido dadas como [u, v, cost]. Algunas carreteras pagan un reembolso, así que su costo es negativo, pero ningún ciclo de carreteras tiene un total negativo. Devuelve el costo más barato desde el pueblo src hasta cada pueblo, usando None para los pueblos a los que no se puede llegar.

Ejemplos

Input:  n = 4, roads = [[0, 1, 4], [0, 2, 5], [2, 1, -3], [1, 3, 2]], src = 0
Output: [0, 2, 5, 4]
Por qué: ir de 0 a 2 y luego a 1 cuesta 5 - 3 = 2, menos que la carretera directa a 1, que cuesta 4
Input:  n = 3, roads = [[0, 1, -2]], src = 0
Output: [0, -2, None]
Por qué: ninguna carretera llega al pueblo 2
Input:  n = 1, roads = [], src = 0
Output: [0]
Por qué: caso límite: llegar al pueblo de inicio no cuesta nada

Pistas

0 / 3

Tiempo objetivo
O(n · m)
Espacio objetivo
O(n)

Restricciones

  • towns are numbered 0 to n - 1
  • road costs may be negative
  • no loop of roads has a negative total

¿Lo que te frena es la idea y no el código? Bellman-Ford lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio