İçeriğe geç

İndirimli yollarla en kısa yollar

Kolay#bellman-ford#negative-edges~20 dk

Görev tanımı

Problem

Bir bölgede 0'dan n - 1'e kadar numaralanmış n kasaba ve [u, v, cost] biçiminde tek yönlü yollar var. Bazı yollar indirim ödüyor, yani maliyetleri negatif; ama hiçbir yol döngüsünün toplamı negatif değil. src kasabasından her kasabaya en ucuz maliyeti döndür; ulaşılamayan kasabalar için None kullan.

Örnekler

Input:  n = 4, roads = [[0, 1, 4], [0, 2, 5], [2, 1, -3], [1, 3, 2]], src = 0
Output: [0, 2, 5, 4]
Neden: 0'dan 2'ye, oradan 1'e gitmek 5 - 3 = 2 tutar; 4 tutan 1'e doğrudan yoldan ucuz
Input:  n = 3, roads = [[0, 1, -2]], src = 0
Output: [0, -2, None]
Neden: 2 numaralı kasabaya giden yol yok
Input:  n = 1, roads = [], src = 0
Output: [0]
Neden: edge case: başlangıç kasabasına ulaşmak hiçbir şeye mal olmaz

İpuçları

0 / 3

Hedef zaman
O(n · m)
Hedef alan
O(n)

Kısıtlar

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

Kodda değil de fikirde mi takıldın? Bellman-Ford bunu anlatıyor.

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