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تمريرات كهذه.في كل تمريرة، اقرأ الأسعار من التمريرة السابقة واكتب في نسخة منها. إذا حدّثت الأسعار في مكانها، فقد تعتمد رحلة على سعر تم تحديده في التمريرة نفسها، وبذلك تتسلل رحلتان في تمريرة واحدة.
الحل
هذا أقصر مسار مع حدّ أقصى لعدد الرحلات. تفشل خوارزمية Dijkstra عند تطبيقها على المدن وحدها، لأن أرخص طريقة للوصول إلى مدينة قد تستهلك محطات التوقف التي يحتاجها باقي الرحلة. تناسب خوارزمية 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 bestخوارزمية Bellman-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. - تشغيل خوارزمية Dijkstra العادية على المدن. مع
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
ما التعقيد الزمني لمسألة أرخص الرحلات الجوية ضمن K محطات توقف؟
تستغرق خوارزمية Bellman-Ford عند تقييدها بـ k+1 جولات زمنًا قدره O(k · E) لعدد E من الرحلات، وتستخدم مساحة إضافية قدرها O(n) لمصفوفتَي الأسعار. إذا لم تغيّر إحدى الجولات شيئًا، فستمرّر الأسعار نفسها إلى الجولة التالية، لذا يمكنك التوقف مبكرًا.
لماذا لا تعمل خوارزمية ديكسترا في مسألة أرخص الرحلات الجوية ضمن K محطات توقف؟
يحتفظ Dijkstra بأفضل سعر واحد لكل مدينة، ولا يعود أبدًا إلى مدينة حُسمت. هنا، قد يكون الطريق الأعلى تكلفة إلى مدينة هو المفيد، إذا كان يتطلب عددًا أقل من الرحلات الجوية. يعمل Dijkstra مجددًا على الحالات (المدينة، الرحلات الجوية المستخدمة)، ما يضاعف عدد الحالات بمقدار 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