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)\)$ という「重み(=時間)が非負の辺」になるので、普通のダイクストラ法がそのまま使えます。
なお「同じ都市や路線を何度でも通過できる」とありますが、使った金額は単調増加するので状態が循環することはなく、無限に安く/速くなることはありません。素直に最短経路問題として扱えます。
アルゴリズム
- 入力を読み、各路線 \(i\) について
- コスト \(2A_i\)、時間 \(S_i\) の辺
- コスト \(2B_i\)、時間 \(T_i\) の辺 を無向辺として両方向に追加する(コストが \(K\) を超える辺は絶対使えないので捨ててよい)。
dist[v][c]を \(\infty\) で初期化し、dist[1][0] = 0として優先度付きキューに \((0, 1, 0)\) を入れる。- キューから時間最小の状態 \((d, u, c)\) を取り出す。
d != dist[u][c]なら古い情報なのでスキップ(遅延削除)。 - \(u\) から出る各辺について、新しい金額 \(nc = c + \text{cost}\) が \(K\) を超えるならスキップ。そうでなければ \(nd = d + \text{time}\) で
dist[to][nc]を更新できるなら更新してキューに入れる。 - 最後に \(\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: