Official

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: