Cheapest Flights Within K Stops
יש n ערים, שממוספרות מ־0 עד n-1, ורשימה של טיסות בכיוון אחד: flights[i] = [from, to, price] היא טיסה מהעיר from לעיר to שעולה price.
החזירו את המחיר הכולל הנמוך ביותר של נסיעה מ־src ל־dst שעוברת דרך לכל היותר k תחנות ביניים, כלומר לכל היותר k+1 טיסות. אם אין נסיעה כזאת, החזירו -1.
פונקציה
- ninteger
- מספר הערים
- flightsinteger-2d-array
- הטיסות בכיוון אחד, כל אחת בתור [from, to, price]
- srcinteger
- העיר שבה הטיול מתחיל
- dstinteger
- העיר שבה הטיול מסתיים
- kinteger
- מספר התחנות המרבי המותר בין src ל-dst
- מחזירהinteger
- המחיר הנמוך ביותר של נסיעה עם לכל היותר k עצירות, או -1
אילוצים
2 ≤ n ≤ 10001 ≤ flights.length ≤ 4500flights[i] = [from, to, price]כאשר0 ≤ from, to < nו-from ≠ to1 ≤ price ≤ 104- אין שתי טיסות שחולקות גם את
fromוגם אתto. 0 ≤ src, dst < nוגםsrc ≠ dst0 ≤ k < n
דוגמאות
- קלט
- n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 1
- פלט
- 230
- הסבר
- עצירה אחת מאפשרת שתי טיסות:
0 → 1 → 3עולה 50 + 180 = 230, ו־0 → 2 → 3עולה 200 + 50 = 250. המסלול הזול יותר,0 → 1 → 2 → 3, כולל שתי עצירות.
- קלט
- n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 2
- פלט
- 150
- הסבר
- שתי עצירות מאפשרות שלוש טיסות, לכן
0 → 1 → 2 → 3מותר עכשיו, והעלות היא 50 + 50 + 50 = 150.
- קלט
- n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 0
- פלט
- -1
- הסבר
- ללא עצירות, הנסיעה חייבת להיות טיסה יחידה מ־0 ל־3, ואין כזו.
שאלת המשך
איך תחזיר את הערים שבטיול הזול ביותר וגם את מחירו?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
ייתכן שלנסיעה הזולה ביותר בסך הכול יהיו יותר מדי עצירות, ולכן מסלול קצר ביותר בלבד אינו מספיק. מחיר שימושי רק בצירוף מספר הטיסות שנדרשו.
נסמן את
cost[c]כמחיר הזול ביותר להגיע לעירcעם לכל היותרrטיסות. מעבר אחד על כל טיסה הופך אותו למחיר הזול ביותר עם לכל היותרr+1טיסות. דרושים לךk+1מעברים כאלה.בכל מעבר, קרא את המחירים מהמעבר הקודם וכתוב לעותק. אם תעדכן במקום, טיסה יכולה להתבסס על מחיר שנקבע באותו מעבר, ומעבר אחד עלול להגניב פנימה שתי טיסות.
פתרון
זהו מסלול קצר ביותר עם מגבלה על מספר הטיסות. האלגוריתם של דייקסטרה על ערים בלבד נכשל, כי הדרך הזולה ביותר להגיע לעיר עשויה לנצל עצירות שנחוצות להמשך הנסיעה. Bellman-Ford מתאים למגבלה: סבב r מוצא את המחיר הזול ביותר עם לכל היותר r טיסות, ולכן מריצים k+1 סבבים.
נסו כל מסלול עם לכל היותר k+1 טיסות
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
עבור בכל מסלול מ־src באמצעות מחסנית של (עיר, מחיר, טיסות שנוצלו). מסלול שמגיע ל־dst מתעד את מחירו ומסתיים, כי כל המחירים חיוביים. מסלול עם k+1 טיסות נזנח; כל מסלול אחר מורחב באמצעות כל טיסה היוצאת מהעיר שלו. כך נבנית כל נסיעה מותרת, ולכן המחיר הטוב ביותר שתועד הוא הנכון.
מספר המסלולים גדל כמו d בחזקת k+1, כאשר יש d טיסות היוצאות מעיר. עם 4 טיסות בכל עיר ו־k = 29, מדובר ב־4^30 ≈ 1.2 × 10^18 מסלולים.
אלגוריתם
- קבץ את הטיסות לפי עיר המוצא.
- דחוף
(src, 0, 0): עיר, מחיר עד כה, מספר הטיסות שנלקחו. - שלוף מסלול. אם העיר שלו היא
dst, שמור את המחיר שלו אם הוא הטוב ביותר עד כה. - אחרת, אם הוא כולל פחות מ-
k+1טיסות, דחוף מסלול ארוך יותר אחד עבור כל טיסה שיוצאת מהעיר שלו. - כשהמחסנית ריקה, החזר את המחיר הטוב ביותר, או -1 אם אף מסלול לא הגיע אל
dst.
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 bestBellman-Ford מוגבל ל־k+1 סבבים
האינטואיציה
נסמן cost[c] כמחיר הזול ביותר להגיע לעיר c עם לכל היותר r טיסות. כאשר r = 0, רק אל src אפשר להגיע, במחיר 0. נסיעה אל a עם לכל היותר r טיסות, ואחריה טיסה a → b, היא נסיעה אל b עם לכל היותר r+1 טיסות, ולכן בכל סבב מציעים עבור כל טיסה את cost[a] + price לעיר b. אחרי k+1 סבבים, cost[dst] היא התשובה.
בכל סבב קוראים את המחירים מהסבב הקודם וכותבים לעותק, כך שמחיר שנקבע במהלך סבב אינו יכול לשמש לטיסה נוספת באותו סבב. בדוגמה הראשונה עם k = 1, המחיר לעיר 2 יורד ל־100 בסבב 2, אבל לא נותר סבב להמשיך בטיסה לעיר 3 במחיר 150.
בכל סבב עוברים פעם אחת על כל טיסה: זמן O(k · E) עבור E טיסות, וזיכרון O(n) עבור שני המערכים.
אלגוריתם
- הגדר את
cost[src] = 0ואת כל ערכיcostהאחרים לאינסוף. - חזור על הפעולות
k+1פעמים: העתק אתcostלתוךnext. - עבור כל טיסה
[a, b, price]שעבורהcost[a]סופי, אםcost[a] + price < next[b], הגדרnext[b] = cost[a] + price. - החלף את
costב-next, ועצור מוקדם אם לא חל שינוי. - החזר את
cost[dst], או -1 אם הוא עדיין אינסוף.
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]
מלכודות ומקרי קצה
- סופרים עצירות כטיסות.
kעצירות פירושןk+1טיסות ו-k+1סבבים. - עדכון במקום. עם
0 → 1,1 → 2,2 → 3בעלות של 1 כל אחת, בסדר הזה, וגם0 → 3בעלות של 500 ו-k = 0, סבב אחד משרשר שלוש טיסות ומחזיר 3, לא 500. - הרצת דייקסטרה רגילה על ערים. עם
0 → 1ו-1 → 2בעלות של 1 כל אחת,0 → 2בעלות של 40,2 → 3בעלות של 1 ו-k = 1, האלגוריתם קובע את העלות לעיר 2 כ-2 אחרי שתי טיסות ומחמיץ את המסלול0 → 2 → 3בעלות של 41. - טיסה מעיר שעדיין לא הגענו אליה. כשמשתמשים באינסוף בתור המספר השלם הגדול ביותר,
cost[a] + priceגולש לערך שלילי ב-32 סיביות. יש לוודא תחילה ש-cost[a]סופי.
שאלות נפוצות3
מהי סיבוכיות הזמן של Cheapest Flights Within K Stops?
Bellman-Ford שמוגבל ל-k+1 סבבים דורש זמן O(k · E) עבור E טיסות, ו-O(n) מקום נוסף עבור שתי מערכי מחירים. סבב שלא משנה דבר מעביר לסבב הבא את אותם המחירים, כך שאפשר לעצור מוקדם.
למה האלגוריתם של דייקסטרה לא עובד למציאת הטיסות הזולות ביותר עם עד K עצירות?
דייקסטרה שומר את המחיר הטוב ביותר לכל עיר ואינו מבקר שוב בעיר שכבר נקבעה. כאן, דרך יקרה יותר לעיר יכולה להיות שימושית, אם היא כללה פחות טיסות. דייקסטרה עובד שוב על מצבים (עיר, מספר הטיסות שנעשה בהן שימוש), מה שמכפיל את מספר המצבים פי k+1.
האם תוכל לפתור את בעיית הטיסות הזולות ביותר עם עד K עצירות באמצעות BFS?
כן. רמה r מכילה את הערים שהגענו אליהן בדיוק לאחר r טיסות, עם המחירים שלהן. יש להוסיף עיר לרמה הבאה רק כשהמחיר החדש שלה נמוך מהמחיר הטוב ביותר שנמצא עבורה, ולעצור לאחר k+1 רמות. מתקבלת אותה תשובה כמו באלגוריתם Bellman-Ford, אבל עוקבים רק אחר טיסות שיוצאות מערים שהמחיר שלהן השתנה.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def findCheapestPrice(n, flights, src, dst, k):
# כתבו כאן קודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנטים
n = 4 flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]] src = 0 dst = 3 k = 1
הפלט הצפוי
230