Official

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\) のまま移動できることもないため、状態遷移において運賃が同じ状態の間でサイクル(閉路)が生じません。 したがって、「これまでに消費した運賃」の小さい順に状態を確定させていく動的計画法が適用できます。

アルゴリズム

  1. \(K' = \lfloor K / 2 \rfloor\) を計算します。
  2. 入力から \(4M\) 本の有向辺(各路線について普通列車の往復 \(2\) 本、特急列車の往復 \(2\) 本)を構築します。 それぞれの辺は \((\text{移動元 } u, \text{移動先 } v, \text{運賃 } \text{cost}, \text{所要時間 } \text{time})\) を持ちます。
  3. 以下の DP テーブルを定義します:
    • \(\text{dp}[c][u] := \) 消費した運賃の合計が \(c\) で、現在都市 \(u\) にいるときの所要時間の最小値
    • 初期値: 全要素を \(\infty\) とし、スタート地点である \(\text{dp}[0][\text{都市 } 1] = 0\) とします。
  4. 運賃 \(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})\)$
  5. 答えの取得:
    • 運賃 \(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: