E - 鉄道旅行 / Railway Trip Editorial by admin Editorial for printing
Gemini 3.8 Flash (High)Overview
This problem asks for the minimum total travel time from City \(1\) to City \(N\) under the constraint that the total fare for \(2\) people is at most \(K\) yen. By noting that the fare paid always increases by at least \(2\) yen with each move, we can solve this problem using Dynamic Programming (DP) where the state maintains the “total fare paid so far.”
Analysis
1. State Expansion
In a standard shortest path problem, we only keep track of the “current city” as the state to minimize travel time. However, in this problem, we have the constraint that the “total fare is at most \(K\) yen.” When a constraint and an objective to minimize are separated like this, it is standard practice to use a “shortest path on an extended graph” or “dynamic programming (DP)” by including the constrained value in the state.
Looking at the constraints, \(K \leq 1000\) and \(N \leq 200\) are relatively small. Therefore, if we define the state as “currently at city \(u\), with a total fare paid of \(c\) yen,” the number of states is \(N \times (K + 1) \approx 200 \times 1001 \approx 2 \times 10^5\), which is small enough to fit easily in memory.
2. Why Dijkstra’s Algorithm Is Not Needed
While Dijkstra’s algorithm is commonly used for shortest path problems on graphs, this problem can be solved with simple dynamic programming that iterates over the fare \(c\).
This is because each line costs \(A_i, B_i \geq 1\) yen per person, meaning it always costs at least \(2A_i, 2B_i \geq 2\) yen for \(2\) people. Since the fare paid strictly increases (by at least \(+2\)) with each move, there are no transitions that decrease the total fare (no negative cycles or zero-cost loops). Consequently, simply updating states in increasing order of fare \(c\) from \(0\) to \(K\) guarantees that transitions are always made from an already optimal state to subsequent states.
Algorithm
Graph Construction:
- For each line, there are \(2\) modes of travel: “local train” and “express train”.
- The fares for \(2\) people are \(2A_i\) yen and \(2B_i\) yen, respectively.
- Since travel is bidirectional, add \(2\) directed edges (\(U_i \to V_i\) and \(V_i \to U_i\)) for each train type (a total of \(4\) directed edges per line).
DP Table Definition:
dp[u][c]: The minimum travel time to be at city \(u\) having paid a total fare of \(c\) yen.- Initial values:
- Starting point:
dp[1][0] = 0 - All other states: \(\infty\) (unreachable)
- Starting point:
DP Transitions:
- Loop over the fare \(c\) in ascending order from \(0\) to \(K\).
- For each city \(u\), if
dp[u][c] != INF, update all outgoing edges from \(u\) (destination \(v\), fare \(\text{cost}\), travel time \(\text{time}\)) as follows:- If \(c + \text{cost} \leq K\): $\(\text{dp}[v][c + \text{cost}] = \min(\text{dp}[v][c + \text{cost}], \text{dp}[u][c] + \text{time})\)$
Calculating the Answer:
- Find the minimum travel time to reach city \(N\) with a total fare of at most \(K\) yen: \(\min_{0 \leq c \leq K} \text{dp}[N][c]\).
- If city \(N\) was never reached (the minimum value remains \(\infty\)), output
-1; otherwise, output the minimum value.
Complexity
- Time Complexity: \(O(K \cdot M)\)
- The loop over the fare \(c\) runs \(K + 1\) times.
- For each \(c\), we iterate over all outgoing edges from all cities. Since each line has \(4\) directed edges, the total number of edges traversed per iteration is \(4M\).
- Therefore, the overall time complexity is \(O(K \cdot M)\).
- Given the constraints \(K \leq 1000\) and \(M \leq 500\), the number of operations is at most around \(1000 \times 2000 \approx 2 \times 10^6\), which runs well within the typical 2-second time limit.
- Space Complexity: \(O(N \cdot K + M)\)
- The DP table size is \((N + 1) \times (K + 1)\), containing approximately \(200 \times 1000\) elements.
- The adjacency list representing the graph takes \(O(N + M)\) space.
- In total, it takes only a few megabytes, which easily satisfies the memory limit.
Implementation Notes
Doubling the Fares: The fares \(A_i, B_i\) given in the problem statement are “per person.” Be sure to use \(2A_i\) and \(2B_i\) since \(2\) people are traveling.
Integer Overflow: The travel times \(S_i, T_i\) of each line can be up to \(10^9\). Taking multiple lines can cause the sum of travel times to exceed the maximum value of a 32-bit signed integer (approximately \(2 \times 10^9\)). Therefore, 64-bit integer types (
long longin C++) must be used for DP values and the infinity constant.Source Code
#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;
}
This editorial was generated by gemini-3.8-flash-high.
posted:
last update: