Official

E - 鉄道旅行 / Railway Trip Editorial by admin Editorial for printing

gpt-6-astra-medium

概要

運賃の総額を所持金以下に抑えながら、都市 \(1\) から都市 \(N\) までの最短所要時間を求めます。
「支払った運賃」と「現在の都市」を状態とする動的計画法(DP)で解けます。

考察

1 人分の運賃だけを管理する

2 人は必ず同じ列車に乗るため、支払う運賃の総額は常に「1 人分の運賃の合計」の \(2\) 倍です。

そこで、1 人分の予算を \(C=\lfloor K/2 \rfloor\) とします。以降は、普通列車の運賃を \(A_i\)、特急列車の運賃を \(B_i\) として、運賃の合計が \(C\) 以下になる移動を考えればよいです。

制約より \(C \leq 500\) なので、使った運賃をすべて列挙することができます。

都市だけでなく、使った運賃も状態に含める

各都市までの最短時間だけを記録する方法では、正しい答えを求められません。

例えば、ある都市までの移動方法として、次の 2 通りがあるとします。

  • 運賃 \(5\) 円、所要時間 \(2\) 分
  • 運賃 \(2\) 円、所要時間 \(4\) 分

前者の方が速いですが、残りの予算が少なくなります。その先の運賃によっては、後者からしか目的地に到達できない場合があります。

つまり、時間が最短の移動だけを残すのではなく、使った運賃ごとに最短時間を管理する必要があります。経路と列車の選び方をすべて列挙する方法も、候補が非常に多くなるため現実的ではありません。

運賃が必ず増えることを利用する

元の鉄道網には閉路があり、同じ都市を何度も訪れることもできます。しかし、各列車の運賃は必ず \(1\) 以上なので、列車に乗るたびに使った運賃は必ず増えます。

したがって、状態を「使った運賃、現在の都市」とすると、遷移先の運賃は必ず遷移元より大きくなります。

この性質により、使った運賃が小さい順に DP を更新するだけでよく、ダイクストラ法などは不要です。

アルゴリズム

1. 移動の選択肢を辺として登録する

各路線について、次の 2 種類の移動を別々の辺として扱います。

  • 普通列車:運賃 \(A_i\)、所要時間 \(S_i\)
  • 特急列車:運賃 \(B_i\)、所要時間 \(T_i\)

どちらも双方向に登録します。運賃が \(C\) を超える列車は一度も利用できないため、登録する必要はありません。

2. DP を定義する

\(dp[c][v]\) を、次の値とします。

都市 \(1\) から都市 \(v\) まで、1 人分の運賃をちょうど \(c\) 円使って移動するときの、所要時間の最小値

到達できない状態の値は \(\mathrm{INF}\) とします。

初期状態は \(dp[0][1]=0\) で、それ以外はすべて \(\mathrm{INF}\) です。なお、コードでは都市番号を \(0\) 始まりにしているため、初期状態は dp[0][0] = 0 です。

3. 運賃が小さい順に更新する

\(c=0,1,\ldots,C\) の順に、各都市 \(v\) の状態を処理します。

\(dp[c][v]\) が到達可能で、都市 \(v\) から都市 \(u\) への列車の運賃が \(a\)、所要時間が \(t\) のとき、\(c+a \leq C\) なら次の更新を行います。

\(dp[c+a][u] \leftarrow \min\bigl(dp[c+a][u],\ dp[c][v]+t\bigr)\)

\(a \geq 1\) なので、更新先は必ず後で処理する状態になります。

また、運賃 \(c\) の状態に到達する移動は、最後に必ず運賃が \(c\) より小さい状態から遷移してきます。それらはすべて先に処理されているため、この順序で正しく最短時間を求められます。

4. 答えを求める

予算を使い切る必要はないため、答えは \(\min_{0 \leq c \leq C} dp[c][N]\) です。

すべて \(\mathrm{INF}\) なら、予算内で到達する方法がないので -1 を出力します。

計算量

\(C=\lfloor K/2 \rfloor\) とします。各路線から登録する辺は最大 \(4\) 本なので、辺数は \(O(M)\) です。

  • 時間計算量: \(O((C+1)(N+M))\)
  • 空間計算量: \(O((C+1)N+M)\)

各運賃について全都市とその隣接辺を調べます。空間は主に DP テーブルと隣接リストに使用します。

実装のポイント

  • 所要時間には 64 ビット整数を使う
    1 回の乗車時間が最大 \(10^9\) 分なので、合計は 32 ビット整数の範囲を超える場合があります。コードでは long long を使用しています。

  • 普通列車と特急列車を両方考慮する
    特急列車の方が速い、普通列車の方が安いとは限りません。名前による決めつけをせず、それぞれ独立した移動として登録します。

  • 到達不能な状態からは更新しない
    dp[cost][v] == INF の場合は処理を飛ばします。

  • 運賃のループを外側に置く
    運賃が小さい状態から順番に処理することが、この DP の正しさを支えています。

  • \(K=0\) や \(K=1\) もそのまま処理できる
    この場合は \(C=0\) です。運賃はすべて正なので列車に乗れず、都市 \(N\) には到達できないため -1 になります。

    ソースコード

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to;
    int cost;
    long long time;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    cin >> N >> M >> K;

    const int budget = K / 2;
    vector<vector<Edge>> graph(N);

    for (int i = 0; i < M; ++i) {
        int u, v, a, b;
        long long s, t;
        cin >> u >> v >> a >> b >> s >> t;
        --u;
        --v;

        if (a <= budget) {
            graph[u].push_back({v, a, s});
            graph[v].push_back({u, a, s});
        }
        if (b <= budget) {
            graph[u].push_back({v, b, t});
            graph[v].push_back({u, b, t});
        }
    }

    constexpr long long INF = (1LL << 62);
    vector<vector<long long>> dp(budget + 1, vector<long long>(N, INF));
    dp[0][0] = 0;

    for (int cost = 0; cost <= budget; ++cost) {
        for (int v = 0; v < N; ++v) {
            if (dp[cost][v] == INF) continue;

            for (const auto& e : graph[v]) {
                int next_cost = cost + e.cost;
                if (next_cost > budget) continue;

                dp[next_cost][e.to] = min(
                    dp[next_cost][e.to],
                    dp[cost][v] + e.time
                );
            }
        }
    }

    long long answer = INF;
    for (int cost = 0; cost <= budget; ++cost) {
        answer = min(answer, dp[cost][N - 1]);
    }

    cout << (answer == INF ? -1 : answer) << '\n';
    return 0;
}

この解説は gpt-6-astra-medium によって生成されました。

posted:
last update: