Official

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

Claude Opus 5 (High)

概要

各辺に「2 種類の(運賃, 所要時間)の選択肢」がある無向グラフで、運賃の合計を \(K\) 円以下に抑えつつ都市 \(1\) から都市 \(N\) へ行く最短時間を求める問題です。「現在いる都市」と「使った金額」を組にした状態でのダイクストラ法(拡張ダイクストラ) で解けます。

考察

気づき 1:運賃は 2 人分なので 2 倍する

\(i\) 番目の路線を普通列車で使うと \(2A_i\) 円、特急列車で使うと \(2B_i\) 円かかります。以降は最初から \(2A_i, 2B_i\) を「その辺のコスト」として扱えば、2 人という設定は忘れて 1 人分の問題として考えられます。

気づき 2:単純なダイクストラでは解けない

もし予算の制約がなければ、各辺について \(\min(S_i, T_i)\) を辺の重みとして普通のダイクストラをすれば終わりです。しかし予算制約があるため、

  • 「時間が短いが高い列車」を選ぶと、後で別の区間で金が足りなくなる
  • 逆に「安いが遅い列車」を選ぶことで、全体としては速くなることもある

というトレードオフが生じます。つまり 「都市 \(v\) に着いた時点の最短時間」だけでは状態が足りません。同じ都市 \(v\) に着くにしても、「300 円使って 10 分で着いた」と「100 円使って 50 分で着いた」のどちらが有利かは、その後の行程に依存します。

気づき 3:使った金額を状態に持つ

そこで、状態を

\[\text{dist}[v][c] = \text{都市 } v \text{ に「合計 } c \text{ 円使った状態」で到達するのに必要な最短時間}\]

と定義します。\(K \leq 1000\) と小さいので、\(c\) は \(0\) から \(K\) までの \(K+1\) 通りしかありません。状態数は \(N \times (K+1) \le 200 \times 1001 \approx 2 \times 10^5\) 程度なので十分間に合います。

この状態空間の上では、辺は $\((v, c) \xrightarrow{\ S_i \ } (u, c + 2A_i), \qquad (v, c) \xrightarrow{\ T_i \ } (u, c + 2B_i)\)$ という「重み(=時間)が非負の辺」になるので、普通のダイクストラ法がそのまま使えます。

なお「同じ都市や路線を何度でも通過できる」とありますが、使った金額は単調増加するので状態が循環することはなく、無限に安く/速くなることはありません。素直に最短経路問題として扱えます。

アルゴリズム

  1. 入力を読み、各路線 \(i\) について
    • コスト \(2A_i\)、時間 \(S_i\) の辺
    • コスト \(2B_i\)、時間 \(T_i\) の辺 を無向辺として両方向に追加する(コストが \(K\) を超える辺は絶対使えないので捨ててよい)。
  2. dist[v][c] を \(\infty\) で初期化し、dist[1][0] = 0 として優先度付きキューに \((0, 1, 0)\) を入れる。
  3. キューから時間最小の状態 \((d, u, c)\) を取り出す。d != dist[u][c] なら古い情報なのでスキップ(遅延削除)。
  4. \(u\) から出る各辺について、新しい金額 \(nc = c + \text{cost}\) が \(K\) を超えるならスキップ。そうでなければ \(nd = d + \text{time}\) で dist[to][nc] を更新できるなら更新してキューに入れる。
  5. 最後に \(\min_{0 \le c \le K} \text{dist}[N][c]\) を答えとする。これが \(\infty\) のままなら -1 を出力。

具体例のイメージ

都市 \(1-2\) を結ぶ路線が「普通 \(A=1\)(2 人で 2 円)で 100 分」「特急 \(B=400\)(2 人で 800 円)で 1 分」だとします。\(K = 500\) なら特急の辺(800 円)はそもそも作られず、\((1,0) \to (2,2)\) が時間 100 で作られます。\(K = 1000\) なら \((1,0)\to(2,800)\) が時間 1 で作られ、こちらが選ばれます。

計算量

状態数は \(V' = N(K+1)\)、状態遷移(辺)の数は \(E' = 4M(K+1)\)(各路線 2 種類 × 双方向 × 各金額)です。

  • 時間計算量: \(O\big((N K + M K)\log (N K)\big)\) … 最大でも \(500 \cdot 1001 \cdot 4 \approx 2\times10^6\) 本の遷移に \(\log\) が付く程度で高速
  • 空間計算量: \(O(NK + M)\)

実装のポイント

  • 2 倍を忘れない:運賃は「1 人あたり」なので \(2A_i, 2B_i\) を使います(結果として金額は常に偶数になります)。

  • オーバーフローに注意:\(S_i, T_i \le 10^9\) で、経路長は最大 \(K/2 = 500\) 本程度の辺を通るため、時間の合計は \(5\times10^{11}\) 程度になり得ます。int ではなく 64bit 整数(long long)を使いましょう。INF も加算でオーバーフローしない値(例:LLONG_MAX/4)にしておくと安全です。

  • コストが \(K\) を超える辺は最初から追加しない:これでグラフを小さくできますし、遷移時の nc > K チェックと合わせて二重に安全です。

  • 答えは \(c\) 全体の最小値:ちょうど \(K\) 円使う必要はないので、\(\text{dist}[N][c]\) を \(c = 0 \ldots K\) で最小化します。

  • 多重辺・自己ループ:同じ都市対を結ぶ路線が複数あってもよいので、隣接行列ではなく隣接リストで持つのが素直です。

  • 到達不能判定は ans >= INF で行い、-1 を出力します。

    ソースコード

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

int main(){
    int N, M, K;
    if(!(cin >> N >> M >> K)) return 0;
    struct E { int to; int cost; long long time; };
    vector<vector<E>> g(N+1);
    for(int i=0;i<M;i++){
        int u,v; long long a,b,s,t;
        cin >> u >> v >> a >> b >> s >> t;
        long long ca = 2*a, cb = 2*b;
        if(ca <= K){
            g[u].push_back({v,(int)ca,s});
            g[v].push_back({u,(int)ca,s});
        }
        if(cb <= K){
            g[u].push_back({v,(int)cb,t});
            g[v].push_back({u,(int)cb,t});
        }
    }
    const long long INF = LLONG_MAX/4;
    // dist[node][spent]
    vector<vector<long long>> dist(N+1, vector<long long>(K+1, INF));
    using P = tuple<long long,int,int>;
    priority_queue<P, vector<P>, greater<P>> pq;
    dist[1][0] = 0;
    pq.push({0,1,0});
    while(!pq.empty()){
        auto [d,u,c] = pq.top(); pq.pop();
        if(d != dist[u][c]) continue;
        for(const auto &e : g[u]){
            int nc = c + e.cost;
            if(nc > K) continue;
            long long nd = d + e.time;
            if(nd < dist[e.to][nc]){
                dist[e.to][nc] = nd;
                pq.push({nd, e.to, nc});
            }
        }
    }
    long long ans = INF;
    for(int c=0;c<=K;c++) ans = min(ans, dist[N][c]);
    if(ans >= INF) cout << -1 << "\n";
    else cout << ans << "\n";
    return 0;
}

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

posted:
last update: