Official

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

Gemini 3.8 Flash (High)

概要

\(2\) 人分の運賃の総額が \(K\) 円以下という制約のもとで、都市 \(1\) から都市 \(N\) への所要時間の総和の最小値を求める問題です。 移動するたびに支払う運賃が必ず \(2\) 円以上増加することに着目し、「これまでに支払った運賃の合計」を状態に持たせた動的計画法(DP)で解くことができます。

考察

1. 状態の拡張

通常の最短経路問題では「現在いる都市」のみを状態として所要時間を最小化しますが、今回は「運賃の合計が \(K\) 円以下」という制約があります。このように制約と最小化対象が分かれている場合は、制約側の値を状態に含める「拡張グラフ上の最短経路問題」あるいは「動的計画法(DP)」を考えるのが定石です。

制約を確認すると \(K \leq 1000, N \leq 200\) と比較的小さい値です。 したがって、「都市 \(u\) にいて、支払った運賃の合計が \(c\) 円」という状態を考えると、状態数は \(N \times (K + 1) \approx 200 \times 1001 \approx 2 \times 10^5\) 通りとなり、配列として十分保持できるサイズです。

2. ダイクストラ法が不要な理由

一般にグラフ上の最短経路問題ではダイクストラ法が用いられますが、今回の問題では運賃 \(c\) についてのループを回す単純な動的計画法で解くことができます。

その理由は、各路線の運賃が \(1\) 人あたり \(A_i, B_i \geq 1\) 円であり、\(2\) 人分では必ず \(2A_i, 2B_i \geq 2\) 円かかるためです。 移動を \(1\) 回行うたびに支払う運賃は必ず真に増加(\(+2\) 以上)するため、運賃の合計が小さくなるような遷移(負の閉路や同一コスト内でのループ)は存在しません。 そのため、運賃 \(c\) を \(0\) から \(K\) まで小さい順に更新していくだけで、常に最適な状態から次の状態へと遷移させることができます。

アルゴリズム

  1. グラフの構築:

    • 各路線につき、「普通列車」と「特急列車」の \(2\) 通りの移動手段が存在します。
    • \(2\) 人分の運賃はそれぞれ \(2A_i\) 円、\(2B_i\) 円です。
    • 双方向に移動可能であるため、それぞれの列車について \(U_i \to V_i\) と \(V_i \to U_i\) の \(2\) 本の有向辺を追加します(\(1\) つの路線あたり計 \(4\) 本の有向辺)。
  2. DPテーブルの定義:

    • dp[u][c]:都市 \(u\) にいて、支払った運賃の総額が \(c\) 円のときの所要時間の最小値
    • 初期値:
      • スタート地点:dp[1][0] = 0
      • それ以外のすべての状態:\(\infty\)(未到達)
  3. DPの遷移:

    • 運賃 \(c\) を \(0\) から \(K\) まで昇順にループします。
    • 各都市 \(u\) について、dp[u][c] != INF であれば、\(u\) から出ているすべての辺(移動先 \(v\)、運賃 \(\text{cost}\)、所要時間 \(\text{time}\))について以下のように更新します:
      • \(c + \text{cost} \leq K\) のとき: $\(\text{dp}[v][c + \text{cost}] = \min(\text{dp}[v][c + \text{cost}], \text{dp}[u][c] + \text{time})\)$
  4. 答えの集計:

    • 都市 \(N\) に運賃 \(K\) 円以下で到達したときの所要時間の最小値 \(\min_{0 \leq c \leq K} \text{dp}[N][c]\) を求めます。
    • 一度も到達できなかった(最小値が \(\infty\) のまま)場合は -1 を、到達できた場合はその最小値を出力します。

計算量

  • 時間計算量: \(O(K \cdot M)\)
    • 運賃 \(c\) のループが \(K + 1\) 回実行されます。
    • 各 \(c\) において、すべての都市から出る辺を走査します。各路線につき有向辺は \(4\) 本あるため、走査する辺の総数は \(4M\) 本です。
    • したがって、全体の時間計算量は \(O(K \cdot M)\) となります。
    • 本問の制約では \(K \leq 1000, M \leq 500\) であるため、計算回数は高々 \(1000 \times 2000 \approx 2 \times 10^6\) 回程度であり、実行時間制限(一般的に 2 秒)に対して非常に高速に動作します。
  • 空間計算量: \(O(N \cdot K + M)\)
    • DPテーブルのサイズが \((N + 1) \times (K + 1)\) であり、約 \(200 \times 1000\) 個の要素を持ちます。
    • グラフを表現する隣接リストのサイズは \(O(N + M)\) です。
    • 全体として数メガバイト程度であり、メモリ制限に対しても十分余裕があります。

実装のポイント

  • 運賃の \(2\) 倍: 問題文で与えられる運賃 \(A_i, B_i\) は「\(1\) 人あたり」の金額です。\(2\) 人分で移動するため、支払う運賃は \(2A_i, 2B_i\) となる点に注意してください。

  • オーバーフロー対策: 各路線の所要時間 \(S_i, T_i\) は最大で \(10^9\) に達します。複数本の路線を乗り継ぐと所要時間の合計が 32-bit 整数の最大値(約 \(2 \times 10^9\))を超えるため、DP配列の値や無限大を表す定数は 64-bit 整数型(C++ の long long)を使用する必要があります。

    ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, K;
    if (!(cin >> N >> M >> K)) return 0;

    vector<vector<Edge>> adj(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v, a, b;
        long long s, t;
        cin >> u >> v >> a >> b >> s >> t;
        // 普通列車
        adj[u].push_back({v, 2 * a, s});
        adj[v].push_back({u, 2 * a, s});
        // 特急列車
        adj[u].push_back({v, 2 * b, t});
        adj[v].push_back({u, 2 * b, t});
    }

    // dp[u][c] : 都市 u にいて、これまでに支払った運賃の合計が c 円のときの所要時間の最小値
    vector<vector<long long>> dp(N + 1, vector<long long>(K + 1, INF));
    dp[1][0] = 0;

    for (int c = 0; c <= K; ++c) {
        for (int u = 1; u <= N; ++u) {
            if (dp[u][c] == INF) continue;
            for (const auto& edge : adj[u]) {
                if (c + edge.cost <= K) {
                    dp[edge.to][c + edge.cost] = min(dp[edge.to][c + edge.cost], dp[u][c] + edge.time);
                }
            }
        }
    }

    long long ans = INF;
    for (int c = 0; c <= K; ++c) {
        ans = min(ans, dp[N][c]);
    }

    if (ans == INF) {
        cout << -1 << "\n";
    } else {
        cout << ans << "\n";
    }

    return 0;
}

この解説は gemini-3.8-flash-high によって生成されました。

posted:
last update: