Cheapest Flights Within K Stops
n şehir vardır; bu şehirler 0 ile n-1 arasında numaralandırılmıştır ve tek yönlü uçuşların listesi verilmiştir: flights[i] = [from, to, price], from şehrinden to şehrine price ücretli bir uçuşu ifade eder.
Yol boyunca en fazla k aktarma, yani en fazla k+1 uçuş içeren src şehrinden dst şehrine bir yolculuğun en düşük toplam ücretini döndürün. Böyle bir yolculuk yoksa -1 döndürün.
Fonksiyon
- ninteger
- şehir sayısı
- flightsinteger-2d-array
- tek yönlü uçuşlar, her biri [from, to, price] biçiminde
- srcinteger
- Gezinin başladığı şehir
- dstinteger
- seyahatin sona erdiği şehir
- kinteger
- src ile dst arasında izin verilen en fazla durak sayısı
- Döndürürinteger
- en fazla k duraklı bir yolculuğun en düşük fiyatı ya da -1
Kısıtlar
2 ≤ n ≤ 10001 ≤ flights.length ≤ 4500flights[i] = [from, to, price]olmak üzere0 ≤ from, to < nvefrom ≠ to1 ≤ price ≤ 104- Hiçbir iki uçuş hem
fromhem detodeğerlerini paylaşmaz. 0 ≤ src, dst < nvesrc ≠ dst0 ≤ k < n
Örnekler
- Girdi
- n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 1
- Çıktı
- 230
- Açıklama
- Bir durak iki uçuşa izin verir:
0 → 1 → 350 + 180 = 230 tutar ve0 → 2 → 3200 + 50 = 250 tutar. Daha ucuz olan0 → 1 → 2 → 3iki durak yapar.
- Girdi
- n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 2
- Çıktı
- 150
- Açıklama
- İki aktarma üç uçuşa izin verir; bu nedenle artık
0 → 1 → 2 → 3yapılabilir ve maliyeti 50 + 50 + 50 = 150 olur.
- Girdi
- n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 0
- Çıktı
- -1
- Açıklama
- Hiç durak olmadan yolculuk, 0'dan 3'e tek bir uçuş olmalıdır; ancak böyle bir uçuş yoktur.
Ek soru
En ucuz seyahatin şehirlerini ve fiyatını nasıl döndürürdünüz?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Toplamda en ucuz yolculukta çok fazla aktarma olabilir, bu nedenle yalnızca en kısa yol yeterli değildir. Bir fiyat, ancak kaç uçuşla ulaşıldığıyla birlikte anlamlıdır.
cost[c], en fazlaruçuşlacşehrine ulaşmanın en düşük maliyeti olsun. Her uçuşun üzerinden bir kez geçmek, bunu en fazlar+1uçuşla ulaşmanın en düşük maliyetine dönüştürür. Böylek+1geçiş yapman gerekir.Her geçişte, fiyatları önceki geçişten oku ve bir kopyaya yaz. Yerinde güncelleme yaparsan, bir uçuş aynı geçişte belirlenen bir fiyatı temel alabilir ve tek geçişte iki uçuş gerçekleşebilir.
Çözüm
Bu, uçuş sayısına sınır konmuş bir en kısa yol problemidir. Yalnızca şehirler üzerinde Dijkstra algoritmasını kullanmak işe yaramaz; çünkü bir şehre ulaşmanın en ucuz yolu, yolculuğun geri kalanı için gereken aktarma haklarını tüketebilir. Bellman-Ford bu sınıra uygundur: r turda en fazla r uçuşla elde edilebilecek en düşük fiyat bulunur, bu nedenle k+1 tur çalıştırırsın.
Her rotayı en fazla k+1 uçuşla dene
Doğru, ama en büyük testlerde bitmiyor
Sezgi
src noktasından başlayan her güzergâhı (şehir, ücret, kullanılan uçuş sayısı) yığınında takip et. dst noktasına ulaşan bir güzergâh ücretini kaydeder ve sona erer; çünkü tüm ücretler pozitiftir. k+1 uçuş içeren bir güzergâhı ele; diğerlerini bulunduğu şehirden kalkan her uçuşla genişlet. İzin verilen her yolculuk oluşturulur, dolayısıyla kaydedilen en düşük ücret doğrudur.
Güzergâh sayısı, bir şehirden d uçuş çıktığında d üzeri k+1 kadar artar. Her şehirden 4 uçuş çıktığında ve k = 29 olduğunda bu, 4^30 ≈ 1.2 × 10^18 güzergâh demektir.
Algoritma
- Uçuşları kalkış şehrine göre grupla.
(src, 0, 0)ekle: şehir, şu ana kadarki ücret, alınan uçuş sayısı.- Bir rotayı çıkar. Şehri
dstise ücretini şimdiye kadarki en iyi ücretse kaydet. - Aksi takdirde,
k+1uçuş sayısından daha az uçuş yaptıysa, şehrinden kalkan her uçuş için bir durak daha uzun bir rota ekle. - Yığın boşaldığında en iyi ücreti döndür;
dsthedefine ulaşan rota yoksa -1 döndür.
def findCheapestPrice(n, flights, src, dst, k):
out = [[] for _ in range(n)]
for a, b, price in flights:
out[a].append((b, price))
best = -1
# Each entry is a route in progress: (city, price so far, flights taken).
stack = [(src, 0, 0)]
while stack:
city, cost, used = stack.pop()
if city == dst:
if best == -1 or cost < best:
best = cost
continue
# k stops allow at most k+1 flights.
if used == k + 1:
continue
for nxt, price in out[city]:
stack.append((nxt, cost + price, used + 1))
return bestk+1 turla sınırlandırılmış Bellman-Ford
Sezgi
cost[c], en fazla r uçuşla c şehrine ulaşmanın en düşük fiyatı olsun. r = 0 iken yalnızca src şehrine ulaşılabilir ve fiyat 0'dır. En fazla r uçuşla a şehrine yapılan bir yolculuğun ardından a → b uçuşu gelirse, en fazla r+1 uçuşla b şehrine ulaşılmış olur. Bu nedenle her turda her uçuş için cost[a] + price değeri b şehrine sunulur. k+1 turdan sonra cost[dst] yanıtı verir.
Her tur, önceki turun fiyatlarını okur ve bir kopyaya yazar; böylece bir turda belirlenen fiyat, aynı turda başka bir uçuş için kullanılamaz. k = 1 olan ilk örnekte, 2. şehir 2. turda 100'e düşer, ancak 150'ye 3. şehre uçmak için başka tur kalmaz.
Her turda her uçuş bir kez okunur: E uçuş için O(k · E) zaman ve iki dizi için O(n) alan gerekir.
Algoritma
cost[src] = 0olarak ayarla ve diğer tümcostdeğerlerini sonsuz yap.k+1kez tekrarla:costdeğerininextiçine kopyala.cost[a]sonlu olan her[a, b, price]uçuşu için,cost[a] + price < next[b]isenext[b] = cost[a] + priceolarak ayarla.costdeğerininextile değiştir ve hiçbir şey değişmediyse erken dur.cost[dst]değerini döndür veya hâlâ sonsuzsa -1 döndür.
def findCheapestPrice(n, flights, src, dst, k):
INF = float("inf")
# cost[c]: the cheapest price to reach city c with the flights allowed so far.
cost = [INF] * n
cost[src] = 0
# Each round allows one more flight; k stops means k+1 flights.
for _ in range(k + 1):
# Read last round's prices and write into a copy,
# so one round can never chain two flights.
nxt = cost[:]
changed = False
for a, b, price in flights:
if cost[a] != INF and cost[a] + price < nxt[b]:
nxt[b] = cost[a] + price
changed = True
cost = nxt
if not changed:
break
return -1 if cost[dst] == INF else cost[dst]
Tuzaklar ve uç durumlar
- Aktarmaları uçuş olarak saymak.
kaktarma,k+1uçuş vek+1tur demektir. - Yerinde güncelleme. Her biri 1 maliyetli
0 → 1,1 → 2,2 → 3uçuşları bu sırayla ve 500 maliyetli0 → 3uçuşu olduğunda,k = 0için bir turda art arda üç uçuş yapılır ve 500 değil, 3 döndürülür. - Şehirler üzerinde doğrudan Dijkstra çalıştırmak. Her biri 1 maliyetli
0 → 1ve1 → 2uçuşları, 40 maliyetli0 → 2uçuşu ve 1 maliyetli2 → 3uçuşu olduğunda,k = 1için algoritma iki uçuşun ardından 2. şehri 2 maliyetle kesinleştirir ve 41 maliyetli0 → 2 → 3yolunu kaçırır. - Henüz ulaşılmamış bir şehirden uçmak. En büyük int değeri olarak sonsuzluk kullanıldığında,
cost[a] + price32 bitte negatif değere taşar. Öncecost[a]değerinin sonlu olup olmadığını kontrol et.
Sıkça sorulan sorular3
En Fazla K Duraklı En Ucuz Uçuşlar probleminin zaman karmaşıklığı nedir?
k+1 turla sınırlı Bellman-Ford, E uçuş için O(k · E) zaman alır ve iki fiyat dizisi için O(n) ek alan kullanır. Hiçbir şeyi değiştirmeyen bir tur, sonraki tura aynı fiyatları aktarır; bu nedenle erken durabilirsin.
Dijkstra'nın algoritması K Durak İçinde En Ucuz Uçuşlar için neden işe yaramaz?
Dijkstra her şehir için en iyi tek fiyatı tutar ve kesinleşmiş bir şehri yeniden ziyaret etmez. Burada, daha az uçuş gerektirdiği için bir şehre ulaşmanın daha pahalı yolu işe yarayabilir. Dijkstra, (şehir, kullanılan uçuş sayısı) durumları üzerinde yeniden çalışır; bu da durum sayısını k+1 ile çarpar.
En Fazla K Duraklı En Ucuz Uçuşlar problemini BFS ile çözebilir misin?
Evet. r seviyesi, tam olarak r uçuşla ulaşılan şehirleri ve ücretlerini içerir. Bir şehri sonraki seviyeye yalnızca yeni ücreti o şehir için şimdiye kadar görülen en iyi ücretten düşükse ekle ve k+1 seviye sonra dur. Bellman-Ford ile aynı yanıtı verir, ancak yalnızca ücreti değişen şehirlerden kalkan uçuşları izler.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def findCheapestPrice(n, flights, src, dst, k):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argümanlar
n = 4 flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]] src = 0 dst = 3 k = 1
Beklenen Çıktı
230