E - 鉄道旅行 / Railway Trip Editorial by admin Editorial for printing
Gemini 3.8 Flash (High)概要
\(2\) 人で所持金 \(K\) 円以内で移動するとき、都市 \(1\) から都市 \(N\) への所要時間の最小値を求める問題です。 各路線の運賃が正整数であり、許容される総運賃が比較的小さいことを利用して、消費した運賃を状態に持つ動的計画法(DP)により解くことができます。
考察
問題の言い換え: \(2\) 人は常に行動を共にするため、各移動で支払う運賃は \(2\) 人分で \(2A_i\) 円または \(2B_i\) 円です。 「\(2\) 人の運賃の総額が \(K\) 円以下」という条件は、「\(1\) 人あたりの運賃の総額が \(\lfloor K / 2 \rfloor\) 円以下」と同値です。 そこで、\(K' = \lfloor K / 2 \rfloor\) とおくと、\(0 \leq K' \leq 500\) となり、考慮すべき運賃の上限が非常に小さくなります。 また、普通列車と特急列車は各路線で独立に選べるため、各路線について普通列車と特急列車の \(2\) 種類、双方向合わせて計 \(4\) 本の有向辺が存在するものとして扱えます。
素朴なアプローチとその課題: 単に都市ごとの最短時間を求めるだけでは、「運賃を多く使って早く着くルート」と「運賃を節約して遅く着くルート」の優劣が決められず、最適な解を得られません。 また、単純な深さ優先探索(DFS)などで全経路を探索すると、同じ都市を行き来できるため探索パターンが指数関数的に増大し、実行時間制限に間に合いません(TLE)。
動的計画法(DP)への帰着: 制約より運賃は \(A_i, B_i \geq 1\) であり、どの列車に乗っても消費運賃は必ず \(1\) 以上増加します。 運賃が減ることも \(0\) のまま移動できることもないため、状態遷移において運賃が同じ状態の間でサイクル(閉路)が生じません。 したがって、「これまでに消費した運賃」の小さい順に状態を確定させていく動的計画法が適用できます。
アルゴリズム
- \(K' = \lfloor K / 2 \rfloor\) を計算します。
- 入力から \(4M\) 本の有向辺(各路線について普通列車の往復 \(2\) 本、特急列車の往復 \(2\) 本)を構築します。 それぞれの辺は \((\text{移動元 } u, \text{移動先 } v, \text{運賃 } \text{cost}, \text{所要時間 } \text{time})\) を持ちます。
- 以下の DP テーブルを定義します:
- \(\text{dp}[c][u] := \) 消費した運賃の合計が \(c\) で、現在都市 \(u\) にいるときの所要時間の最小値
- 初期値: 全要素を \(\infty\) とし、スタート地点である \(\text{dp}[0][\text{都市 } 1] = 0\) とします。
- 運賃 \(c\) を \(0\) から \(K'\) まで昇順に走査し、各辺 \((u, v, \text{cost}, \text{time})\) について緩和(遷移)を行います:
- \(c + \text{cost} \leq K'\) かつ \(\text{dp}[c][u] \neq \infty\) であるとき: $\(\text{dp}[c + \text{cost}][v] = \min(\text{dp}[c + \text{cost}][v], \text{dp}[c][u] + \text{time})\)$
- 答えの取得:
- 運賃 \(0 \leq c \leq K'\) の範囲で、都市 \(N\) に到達したときの最小所要時間 \(\min_{0 \leq c \leq K'} \text{dp}[c][\text{都市 } N]\) を求めます。
- 最小値が \(\infty\) のままであれば到達不可能であるため
-1を出力し、そうでなければその最小値を出力します。
計算量
- 時間計算量: \(O(K \cdot M)\)
- 運賃のループが \(K' + 1 \leq 501\) 回、内側のループで全有向辺 \(4M \leq 2000\) 本を走査します。
- 全体の計算ステップ数は高々 \(500 \times 2000 \approx 10^6\) 回であり、実行時間制限に対して非常に余裕を持って間に合います。
- 空間計算量: \(O(K \cdot N + M)\)
- 状態数 \((K' + 1) \times N \leq 501 \times 200 \approx 10^5\) の配列と、辺のリスト \(4M\) 本を保持するため、省メモリで動作します。
実装のポイント
1次元配列を用いた高速化: Python では \(2\) 次元リスト
dp[c][u]よりも、インデックスを \(c \times N + u\) として \(1\) 次元リストで管理する方がメモリアクセスが局所化され、オーバーヘッドが小さくなり高速に動作します。大きな値の初期化: 所要時間は最大で \(10^9\) オーダーの値が複数回足し合わされるため、最大値は \(10^{11}\) 以上になり得ます。無限大を表す初期値には
float('inf')などの十分大きな値を設定してください。ソースコード
import sys
def solve():
input = sys.stdin.read
data = input().split()
if not data:
return
N = int(data[0])
M = int(data[1])
K = int(data[2])
K_prime = K // 2
edges = []
idx = 3
for _ in range(M):
u = int(data[idx]) - 1
v = int(data[idx + 1]) - 1
a = int(data[idx + 2])
b = int(data[idx + 3])
s = int(data[idx + 4])
t = int(data[idx + 5])
idx += 6
edges.append((u, v, a, s))
edges.append((v, u, a, s))
edges.append((u, v, b, t))
edges.append((v, u, b, t))
INF = float('inf')
dp = [INF] * ((K_prime + 1) * N)
dp[0] = 0
for c in range(K_prime + 1):
base_c = c * N
for u, v, cost, time in edges:
if c + cost <= K_prime:
prev_time = dp[base_c + u]
if prev_time != INF:
nxt_idx = (c + cost) * N + v
new_time = prev_time + time
if new_time < dp[nxt_idx]:
dp[nxt_idx] = new_time
ans = INF
target = N - 1
for c in range(K_prime + 1):
val = dp[c * N + target]
if val < ans:
ans = val
if ans == INF:
print(-1)
else:
print(ans)
if __name__ == '__main__':
solve()
この解説は gemini-3.8-flash-high によって生成されました。
posted:
last update: