E - 鉄道旅行 / Railway Trip Editorial by admin Editorial for printing
gpt-6-astra-medium概要
都市 \(1\) から都市 \(N\) まで、運賃の合計が予算以下になる移動方法のうち、所要時間が最小のものを求めます。
「現在の都市」に加えて「ここまでに使った運賃」を状態として持つ動的計画法で解けます。
考察
1. 予算を1人分に換算する
2人は常に同じ列車に乗るため、支払う運賃の総額は、1人分の運賃の合計のちょうど2倍です。
そこで、1人分の予算を \(C=\lfloor K/2\rfloor\) とします。以降は、普通列車の運賃を \(A_i\)、特急列車の運賃を \(B_i\) として、その合計が \(C\) 以下になる移動を考えれば十分です。
例えば \(K=9\) 円なら、1人分の運賃の合計は \(4\) 円までです。制約より \(C\leq 500\) なので、使用した運賃をすべて状態として管理できます。
2. 都市ごとの最短時間だけでは不十分
通常の最短経路問題のように、各都市への最短時間だけを記録すると正しく解けません。
例えば、ある都市への到着方法として、
- 所要時間は短いが、予算をほとんど使い切る方法
- 所要時間は長いが、運賃を節約できる方法
がある場合、後者でなければ目的地までの運賃が足りない可能性があります。
一方、経路や列車の選び方をすべて列挙すると、候補数が膨大になります。そこで、同じ都市に、同じ運賃で到着した方法のうち、所要時間が最小のものだけを残すことにします。それ以外は、残りの予算も今後選べる移動も同じなので、答えの改善に役立ちません。
3. 運賃が必ず増えることを利用する
すべての列車の運賃は \(1\) 以上です。そのため、列車に乗るたびに使用済み運賃は必ず増えます。
元の鉄道網には閉路がありますが、「都市と使用済み運賃」の組を状態にすると、遷移先の運賃は必ず現在より大きくなります。したがって、使用済み運賃の小さい順にDPを計算できます。
また、普通列車と特急列車の運賃・所要時間に大小関係の保証はありません。名前で判断せず、それぞれを別の移動手段として扱います。
アルゴリズム
1. グラフを作る
各路線について、次の2種類の移動を両方向に追加します。
- 運賃 \(A_i\)、所要時間 \(S_i\) の移動
- 運賃 \(B_i\)、所要時間 \(T_i\) の移動
運賃が \(C\) を超える移動は、1回利用するだけで予算超過になるため、追加する必要はありません。
2. DPを定義する
\(dp[c][v]\) を、次の値とします。
1人分の運賃をちょうど \(c\) 円使って都市 \(v\) に到着するための、所要時間の最小値
初期状態は \(dp[0][1]=0\) とし、それ以外は到達不能を表す \(\infty\) にします。
3. 使用済み運賃の小さい順に更新する
\(c=0,1,\ldots,C\) の順に、各都市 \(u\) からの移動を調べます。
都市 \(u\) から都市 \(v\) へ、運賃 \(f\)、所要時間 \(t\) で移動できるとします。\(c+f\leq C\) なら、次のように更新します。
\(dp[c+f][v]\leftarrow\min\bigl(dp[c+f][v],\ dp[c][u]+t\bigr)\)
\(f\geq 1\) なので、更新先は必ずこれから処理する運賃の行です。
4. 答えを求める
予算を使い切る必要はないため、答えは \(\min_{0\leq c\leq C}dp[c][N]\) です。すべて到達不能なら -1 を出力します。
コードでは、各運賃の行を処理するときに answer を更新しています。さらに、現在の所要時間が answer 以上なら、その状態からの遷移を省略します。どの移動でも所要時間は増えるため、そこから現在の答えを改善することはできません。
正しく求められる理由
同じ都市・同じ使用済み運賃に到達した後は、選べる移動が同じです。そのため、最短時間の方法だけを残しても、最適な移動方法を失いません。
また、運賃 \(c\) の状態へ到着する直前の状態は、必ず使用済み運賃が \(c\) 未満です。運賃の小さい順に処理すれば、必要な遷移をすべて反映してから次へ進めます。
したがって、このDPで予算内の最短時間を求められます。コードの枝刈りも、すでに得られた答えを改善できない状態だけを省略するので、答えに影響しません。
計算量
\(C=\lfloor K/2\rfloor\) とします。
各運賃について \(N\) 都市を確認し、全体で \(O(M)\) 本の移動を調べます。
- 時間計算量: \(O((C+1)(N+M))\)
- 空間計算量: \(O((C+1)N+M)\)
\(C+1\) と表記することで、\(K=0\) の場合も含めています。
実装のポイント
都市番号の変換
コードでは都市番号を \(0\) 始まりにしているため、初期状態はdp[0][0] = 0、目的地はn - 1です。運賃は「ちょうど使用した額」として管理する
答えはdp[budget][target]だけではなく、予算以下のすべての運賃についての最小値です。双方向に辺を追加する
普通列車・特急列車のそれぞれについて、両方向の移動を登録します。多重辺もそのまま扱えます。十分に大きな値を使う
所要時間の合計は32ビット整数に収まらない可能性があります。Pythonの整数は問題なく扱え、コードでは到達不能の値に10**30を使っています。予算が0でも特別扱いは不要
すべての運賃が正なので移動できず、この実装のまま-1が出力されます。ソースコード
import sys
def main():
input = sys.stdin.buffer.readline
n, m, k = map(int, input().split())
budget = k // 2
graph = [[] for _ in range(n)]
for _ in range(m):
u, v, a, b, s, t = map(int, input().split())
u -= 1
v -= 1
if a <= budget:
graph[u].append((v, a, s))
graph[v].append((u, a, s))
if b <= budget:
graph[u].append((v, b, t))
graph[v].append((u, b, t))
inf = 10**30
dp = [[inf] * n for _ in range(budget + 1)]
dp[0][0] = 0
answer = inf
target = n - 1
for cost in range(budget + 1):
row = dp[cost]
if row[target] < answer:
answer = row[target]
for u, current_time in enumerate(row):
if current_time >= answer:
continue
for v, fare, travel_time in graph[u]:
next_cost = cost + fare
if next_cost <= budget:
next_time = current_time + travel_time
next_row = dp[next_cost]
if next_time < next_row[v]:
next_row[v] = next_time
print(answer if answer < inf else -1)
if __name__ == "__main__":
main()
この解説は gpt-6-astra-medium によって生成されました。
posted:
last update: