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: