İki durak arasındaki en ucuz rota
Görev tanımı
Problem
Bir teslimat haritasında 0'dan n - 1'e kadar numaralanmış n durak ve her maliyeti sıfır ya da daha büyük olan [u, v, cost] biçiminde tek yönlü yollar var. src durağından dst durağına sürmenin en ucuz toplam maliyetini döndür; dst'ye ulaşılamıyorsa -1 döndür.
Örnekler
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
Neden: 0'dan 2'ye, 1'e, 3'e, 4'e 1 + 2 + 1 + 3 tutar; tek başına 4 tutan 1'e doğrudan yoldan ucuz
Input: n = 3, roads = [[0, 1, 2]], src = 0, dst = 2
Output: -1
Neden: 2. durağa giden yol yok
Input: n = 2, roads = [[0, 1, 5]], src = 1, dst = 1
Output: 0
Neden: edge case: rota zaten hedefinde
İpuçları
0 / 3
Genişlik öncelikli arama en az yolu bulur, en ucuz toplamı değil. Yollarda maliyetler varken önce hangi durak hakkında emin olabilirsin?
Bilinen maliyeti en küçük olan kesinleşmemiş durak asla ucuzlayamaz, çünkü ona giden diğer her rota zaten en az o kadar tutan bir duraktan geçerdi. Onu kesinleştir ve komşularını güncelle.
(0, src) ile başlayan bir (cost so far, stop) min-heap'i tut. En ucuz elemanı pop et; o durak için daha ucuz bir maliyet zaten biliniyorsa atla, durak dst ise maliyetini döndür. Değilse maliyeti iyileşen her komşuyu push et.
- Hedef zaman
- O((n + m) log n)
- Hedef alan
- O(n + m)
Kısıtlar
- stops are numbered 0 to n - 1
- roads are one-way
- every cost ≥ 0
Çözüm
Dijkstra algoritması durakları en ucuz maliyetlerine göre sırayla kesinleştirir. Hiçbir yolun maliyeti negatif olmadığı için min-heap'in tepesindeki durağa sonradan daha ucuza ulaşılamaz; bu yüzden dst ilk kez pop edildiğinde maliyeti kesindir ve arama durabilir. Daha ucuz rotalar bulundukça bir durak birkaç kez push edilebilir; eski, daha pahalı elemanlar yüzeye çıktıklarında atlanır. m yol için zaman O((n + m) log n), alan 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)) # -> 0Kodda değil de fikirde mi takıldın? Dijkstra algoritması bunu anlatıyor.