Pular para o conteúdo

Menores caminhos com reembolsos

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

A missão

Problema

Uma região tem n cidades numeradas de 0 a n - 1 e estradas de mão única dadas como [u, v, cost]. Algumas estradas pagam um reembolso, então o custo delas é negativo, mas nenhum ciclo de estradas tem total negativo. Retorne o menor custo da cidade src até cada cidade, usando None para as cidades que não podem ser alcançadas.

Exemplos

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 e depois a 1 custa 5 - 3 = 2, menos que a estrada direta até 1, que custa 4
Input:  n = 3, roads = [[0, 1, -2]], src = 0
Output: [0, -2, None]
Por quê: nenhuma estrada leva à cidade 2
Input:  n = 1, roads = [], src = 0
Output: [0]
Por quê: edge case: chegar à cidade inicial não custa nada

Dicas

0 / 3

Tempo-alvo
O(n · m)
Espaço-alvo
O(n)

Restrições

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

Travou na ideia, e não no código? Bellman-Ford explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado