Pular para o conteúdo

Rota mais barata entre duas paradas

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

A missão

Problema

Um mapa de entregas tem n paradas numeradas de 0 a n - 1 e estradas de mão única dadas como [u, v, cost], em que todo custo é zero ou mais. Retorne o menor custo total para dirigir da parada src até a parada dst, ou -1 se dst não puder ser alcançada.

Exemplos

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ê: ir de 0 a 2, depois a 1, a 3 e a 4 custa 1 + 2 + 1 + 3, menos que pegar a estrada direta até 1, que sozinha custa 4
Input:  n = 3, roads = [[0, 1, 2]], src = 0, dst = 2
Output: -1
Por quê: nenhuma estrada leva à parada 2
Input:  n = 2, roads = [[0, 1, 5]], src = 1, dst = 1
Output: 0
Por quê: edge case: a rota já está no destino

Dicas

0 / 3

Tempo-alvo
O((n + m) log n)
Espaço-alvo
O(n + m)

Restrições

  • stops are numbered 0 to n - 1
  • roads are one-way
  • every cost ≥ 0

Travou na ideia, e não no código? Algoritmo de Dijkstra explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado