Rota mais barata entre duas paradas
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
A busca em largura encontra o menor número de estradas, não o menor total. Com custos nas estradas, de qual parada você pode ter certeza primeiro?
A parada não finalizada com o menor custo conhecido nunca pode ficar mais barata, porque qualquer outra rota até ela passaria por uma parada que já custa pelo menos o mesmo. Finalize essa parada e atualize os vizinhos dela.
Mantenha um min-heap de (custo até agora, parada), começando com (0, src). Extraia a entrada mais barata, pule-a se já houver um custo menor conhecido para aquela parada e retorne o custo quando a parada for dst. Caso contrário, insira no heap cada vizinho cujo custo melhore.
- 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
Solução
O algoritmo de Dijkstra finaliza as paradas na ordem do seu menor custo. Como nenhuma estrada tem custo negativo, a parada no topo do min-heap não pode ser alcançada com custo menor depois; então, na primeira vez que dst é extraída, seu custo é definitivo e a busca pode parar. Uma parada pode ser inserida várias vezes conforme aparecem rotas mais baratas, e as entradas mais antigas e mais caras são puladas quando chegam ao topo. Com m estradas, o tempo é O((n + m) log n) e o espaço é 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)) # -> 0Travou na ideia, e não no código? Algoritmo de Dijkstra explica isso.