İçeriğe geç

İki durak arasındaki en ucuz rota

Kolay#dijkstra#min-heap~20 dk

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

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

Kodda değil de fikirde mi takıldın? Dijkstra algoritması bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case