Cheapest Flights Within K Stops
n 個の都市があり、都市には 0 から n-1 まで番号が付けられています。また、片道便のリストがあります。flights[i] = [from, to, price] は、都市 from から都市 to までの、料金が price のフライトを表します。
途中の経由地が最大 k 個、つまりフライトが最大 k+1 便となる、src から dst への旅行の最安総額を返してください。そのような旅行が存在しない場合は、-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- 出発地と到着地の両方が同じフライトは2つありません。
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
- 説明
- 乗り継ぎが1回の場合、2つの経路があります。
0 → 1 → 3の費用は50 + 180 = 230で、0 → 2 → 3の費用は200 + 50 = 250です。より安い0 → 1 → 2 → 3は乗り継ぎが2回になります。
- 入力
- n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 2
- 出力
- 150
- 説明
- 経由地が2つあれば3便を利用できるため、
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までの直通便でなければなりませんが、そのような便はありません。
発展問題
最も安い旅行に含まれる都市とその料金を、どのように返しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
全体として最も安い旅程は乗り継ぎが多すぎる場合があるため、単純な最短経路だけでは不十分です。料金は、利用したフライトの数と合わせて初めて意味を持ちます。
cost[c]を、最大r回のフライトで都市cに到達するための最安値とします。すべてのフライトを1回走査すると、最大r+1回のフライトでの最安値になります。このような走査をk+1回行う必要があります。各パスでは、前のパスの価格を読み取り、コピーに書き込みます。インプレースで更新すると、同じパス内で設定された価格をもとにフライトが追加され、1回のパスで2つのフライトが紛れ込む可能性があります。
解説
これは、フライト数に制限がある最短経路問題です。都市だけを対象にしたダイクストラ法ではうまくいきません。ある都市に到達する最安の経路が、残りの旅程に必要な経由地を使い切ってしまう可能性があるためです。ベルマン・フォード法ならこの制限に対応できます。ラウンド r では、フライト数が最大 r 回のときの最安値を求めるため、k+1 回のラウンドを実行します。
k+1便以内であらゆる経路を試す
正しいが、最大のテストでは終わらない
考え方
src から出発するすべての経路を、(都市、料金、利用したフライト数) のスタックでたどります。dst に到達した経路は料金を記録して終了します。料金はすべて正だからです。フライト数が k+1 の経路は破棄し、それ以外の経路は、その都市から出発するすべてのフライトに延長します。許可されたすべての移動が構築されるため、記録された料金のうち最小のものが答えになります。
都市から出発するフライト数を d とすると、経路は d の k+1 乗のように増えます。各都市に 4 便あり、k = 29 の場合、経路数は 4^30 ≈ 1.2 × 10^18 です。
アルゴリズム
- フライトを出発都市ごとにグループ化します。
(src, 0, 0)をプッシュします：都市、これまでの料金、利用したフライト数。- 経路をポップします。都市が
dstの場合、これまでで最安ならその料金を保持します。 - そうでない場合、利用したフライト数が
k+1未満なら、その都市から出発する各フライトについて、経路を1つ延長してプッシュします。 - スタックが空になったら、最安料金を返します。
dstに到達した経路がなければ-1を返します。
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] を、最大 r 回のフライトで都市 c に到達する最安値とします。r = 0 のとき到達できるのは src のみで、価格は 0 です。最大 r 回のフライトで a に到達し、その後フライト a → b に乗ると、最大 r+1 回のフライトで b に到達できます。そのため、各ラウンドではすべてのフライトについて、cost[a] + price を b への候補として提示します。k+1 ラウンド後の cost[dst] が答えです。
各ラウンドでは前のラウンドの価格を読み取り、コピー先に書き込むため、ラウンド中に設定された価格が同じラウンド内の別のフライトに使われることはありません。k = 1 の最初の例では、ラウンド 2 で都市 2 への価格が 100 に下がりますが、その後都市 3 まで 150 で飛ぶためのラウンドは残っていません。
各ラウンドですべてのフライトを 1 回ずつ読み取ります。フライト数を E とすると、時間計算量は O(k · E)、2 つの配列の空間計算量は O(n) です。
アルゴリズム
cost[src] = 0に設定し、その他すべてのcostを無限大に設定します。k+1回繰り返します。costをnextにコピーします。cost[a]が有限である各フライト[a, b, price]について、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の場合、1ラウンドで3回のフライトが連鎖し、500ではなく3が返されます。 - 都市に対して通常のDijkstraを実行する。
0 → 1と1 → 2の費用がそれぞれ1、0 → 2の費用が40、2 → 3の費用が1で、k = 1の場合、2回のフライト後に都市2までの費用を2として確定し、費用41の0 → 2 → 3を見落とします。 - 未到達の都市から飛び立つ。最大の整数として無限大を使うと、
cost[a] + priceは32ビットで負の値にオーバーフローします。まずcost[a]が有限であることを確認してください。
よくある質問3
K 停留以内的最便宜航班的时间复杂度是多少？
k+1 ラウンドに制限した Bellman-Ford は、E 個のフライトに対して O(k · E) 時間かかり、2 つの料金配列のために O(n) の追加領域を使います。何も変化しないラウンドでは、次のラウンドにも同じ料金が引き継がれるため、早期に停止できます。
なぜダイクストラ法は「K 回の乗り継ぎ以内で最安のフライト」を解けないのでしょうか？
Dijkstra法では各都市について最良の運賃を1つ保持し、確定した都市を再訪することはありません。ここでは、都市までのより高い運賃の経路でも、利用した便数が少なければ役に立つことがあります。Dijkstra法を状態（都市、利用した便数）に対して再び適用すると、状態数はk+1倍になります。
K回以内の乗り継ぎで最安の航空券をBFSで求められますか？
はい。レベル r には、ちょうど r 回のフライトで到達した都市とその運賃が格納されます。新しい運賃がその都市でこれまでに確認された最安運賃を下回る場合にのみ、次のレベルにその都市を追加し、k+1 レベルの後で停止します。Bellman-Fordと同じ答えが得られますが、運賃が変わった都市から出発するフライトだけをたどります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
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