E - 鉄道旅行 / Railway Trip Editorial by admin Editorial for printing
Claude Opus 5 (High)概要
都市を頂点、鉄道路線を辺とするグラフ上で、都市 \(1\) から都市 \(N\) へ移動します。各辺には「運賃・所要時間」の組が \(2\) 通り(普通/特急)あり、運賃の総額が \(K\) 円以下という制約のもとで所要時間の総和を最小化する問題です。
「頂点」に「これまでに使った金額」の情報を付け加えた拡張グラフ(状態グラフ)上のダイクストラ法で解けます。
考察
まず気づくこと:単純な最短経路では解けない
もし予算の制約がなければ、各辺について「所要時間が短い方の列車」を選んで普通のダイクストラ法を行うだけで答えが出ます。
しかし予算があるため、「速いが高い列車」を使いすぎると途中で所持金が尽きてしまいます。つまり、同じ都市に到達しても「いくら使ったか」が違えばその後の選択肢が変わるため、「都市ごとに最短時間を \(1\) つ持つ」という通常のダイクストラでは正しく解けません。
具体例で考えます。都市 \(1 \to 2 \to 3\) という経路があり、
- 辺 \(1\)-\(2\):普通 \(=(運賃 2, 時間 100)\)、特急 \(=(運賃 100, 時間 1)\)
- 辺 \(2\)-\(3\):特急しか安いものがなく、運賃 \(50\) が必要
このとき \(K\) が小さければ、辺 \(1\)-\(2\) で時間 \(1\) の特急に乗ってしまうと辺 \(2\)-\(3\) に乗るお金が残りません。「都市 \(2\) に最短時間で着く方法」だけを覚えていては失敗します。
解決策:状態を (都市, 使った金額) に拡張する
そこで、状態を「今いる都市 \(v\)」と「これまでに使った運賃の合計 \(c\)」の組 \((v, c)\) とします。
- \(c\) の取りうる値は \(0, 1, \dots, K\) の \(K+1\) 通り(\(K \le 1000\))
- 状態数は \((N+1) \times (K+1) \le 201 \times 1001 \approx 2 \times 10^5\) 程度
この状態を頂点とみなしたグラフを作れば、辺のコストは「所要時間」だけになり、通常のダイクストラ法がそのまま使えます。
\(dist[v][c] = \) 「都市 \(v\) に、運賃を合計 \(c\) 円使って到達するための最小所要時間」
遷移
状態 \((u, c)\) から、路線 \(i\)(\(u\) と \(w\) を結ぶ)を使って移動する場合、\(2\) 人分の運賃を払うことに注意して:
- 普通列車:\(c + 2A_i \le K\) なら \((w,\, c + 2A_i)\) へ、時間 \(S_i\) のコスト
- 特急列車:\(c + 2B_i \le K\) なら \((w,\, c + 2B_i)\) へ、時間 \(T_i\) のコスト
運賃は \(2\) 人分なので \(2\) 倍するのが最大の落とし穴です。あらかじめ入力時に \(A_i \leftarrow 2A_i\)、\(B_i \leftarrow 2B_i\) としてしまうと楽です。
同じ都市・路線を何度でも通れることについて
「何度でも通過できる」とありますが、運賃は毎回かかり(\(A_i, B_i \ge 1\) より必ず正)、所要時間も正なので、無限に安く・速くなることはありません。予算 \(K\) が有限なので、拡張グラフ上で使った金額は単調増加し、そもそも同じ状態に戻ることはありません(実は拡張グラフはDAGですが、ダイクストラでそのまま扱えます)。
答え
\(\min_{0 \le c \le K} dist[N][c]\) が答えです。すべて \(\infty\) なら \(-1\) を出力します。
ダイクストラ法では距離の小さい順に状態が確定するので、都市が \(N\) である状態が最初に取り出された瞬間の距離がそのまま答えになり、そこで打ち切れます。
アルゴリズム
- 入力を読み、運賃を \(2\) 倍しておく(\(2\) 人分)。
- 各路線について、\((2A_i, S_i)\) と \((2B_i, T_i)\) の \(2\) 通りの辺候補を、両方向に張る。ただし運賃が \(K\) を超えるものは使えないので捨ててよい。
- 状態 \((v, c)\) を頂点とする拡張グラフ上で、始点 \((1, 0)\) からダイクストラ法を行う。
- 優先度付きキュー(ヒープ)に \((所要時間, 状態)\) を入れる。
- 取り出した状態の都市が \(N\) なら、その所要時間を出力して終了。
- そうでなければ、残り予算 \(K - c\) で乗れる列車すべてについて遷移を試す。
- キューが空になっても都市 \(N\) に到達しなかったら \(-1\)。
実装上の状態のもち方
\((v, c)\) を \(1\) 次元配列のインデックス v * (K+1) + c に潰すと、配列アクセスが速く実装も簡単です(復元は divmod(idx, K+1))。
枝刈り(任意)
\(2A_i \le 2B_i\) かつ \(S_i \le T_i\) なら特急は「高くて遅い」だけなので完全に無駄であり、候補から外せます(逆も同様)。これでヒープに入る辺の数が減り高速化できます。正当性には影響しません。
計算量
拡張グラフの頂点数は \(V' = O(NK)\)、辺数は \(E' = O(MK)\) です(各路線が各予算値ごとに最大 \(2 \times 2 = 4\) 本の辺を持つ)。
- 時間計算量: \(O(MK \log (NK))\) (\(M \le 500\), \(K \le 1000\) より辺数は \(2 \times 10^6\) 程度で、十分間に合います)
- 空間計算量: \(O(NK + M)\) (\(dist\) 配列が \((N+1)(K+1) \approx 2 \times 10^5\)、隣接リストが \(O(M)\))
実装のポイント
運賃は \(2\) 人分:\(A_i, B_i\) をそのまま使うとWAになります。読み込み時に \(2\) 倍しておくのが安全です。\(K\) が奇数の場合もあるので、「\(K\) を \(2\) で割る」のではなく「運賃を \(2\) 倍する」方が誤りにくいです(\(K=5\)、運賃 \(2A=4\) のときなど)。
多重辺がある:同じ都市の組を結ぶ路線が複数あるため、隣接行列ではなく隣接リストで持ちます。
所要時間が大きい:\(S_i, T_i \le 10^9\) で、経路長も予算の分だけ伸びうるので、答えは \(32\) ビットに収まらない可能性があります。C++等では
long longを使ってください(Pythonでは多倍長なので問題なし)。INF の扱い:
INF = 1 << 62のように十分大きな値を使います。ダイクストラの遅延削除:ヒープから取り出したとき
d > dist[idx]ならスキップする、という定番の書き方をします。早期終了:都市 \(N\) の状態を初めて取り出したら即出力して終了できます(予算違いの複数状態を全部走査する必要はありません)。
\(K\) を超える辺の除去:\(2A_i > K\) の列車は最初から使えないので隣接リストに入れないと、無駄な処理が減ります。
到達不可能の判定:\(N\) に一度も到達せずキューが空になったら \(-1\)。例えば \(K\) が小さすぎて最初の \(1\) 本すら乗れない場合もあり得ます。
ソースコード
import sys
import heapq
def main():
data = sys.stdin.buffer.read().split()
p = 0
N = int(data[p]); M = int(data[p+1]); K = int(data[p+2]); p += 3
K1 = K + 1
adj = [[] for _ in range(N + 1)]
for _ in range(M):
u = int(data[p]); v = int(data[p+1])
a = 2 * int(data[p+2]); b = 2 * int(data[p+3])
s = int(data[p+4]); t = int(data[p+5])
p += 6
if a <= b and s <= t:
cand = ((a, s),)
elif b <= a and t <= s:
cand = ((b, t),)
else:
cand = ((a, s), (b, t))
au = adj[u]; av = adj[v]
for c, tm in cand:
if c <= K:
au.append((v, c, tm))
av.append((u, c, tm))
INF = 1 << 62
size = (N + 1) * K1
dist = [INF] * size
start = K1 # node 1, cost 0
dist[start] = 0
heap = [(0, start)]
hpop = heapq.heappop
hpush = heapq.heappush
target = N
while heap:
d, idx = hpop(heap)
if d > dist[idx]:
continue
node, c = divmod(idx, K1)
if node == target:
sys.stdout.write(str(d) + "\n")
return
rem = K - c
base = d
for v, cc, tm in adj[node]:
if cc <= rem:
nd = base + tm
ni = v * K1 + c + cc
if nd < dist[ni]:
dist[ni] = nd
hpush(heap, (nd, ni))
sys.stdout.write("-1\n")
main()
この解説は claude5opus-high によって生成されました。
posted:
last update: