E - 鉄道旅行 / Railway Trip Editorial by admin Editorial for printing
gpt-6-astra-mediumOverview
Find the minimum travel time from city \(1\) to city \(N\) such that the total fare paid does not exceed the money in hand.
This can be solved with dynamic programming (DP) where the state is represented by (fare paid, current city).
Analysis
Managing Only One Person’s Fare
Since both people always take the same train, the total fare paid is always twice the sum of the fare for one person.
Therefore, let the budget for one person be \(C=\lfloor K/2 \rfloor\). From here on, considering the fare for a local train as \(A_i\) and for an express train as \(B_i\), it suffices to consider movements such that the total fare is at most \(C\).
From the constraints, \(C \leq 500\), so we can enumerate all possible amounts of fare spent.
Including Fare Spent in the State in Addition to City
Recording only the shortest time to each city is not sufficient to find the correct answer.
For example, suppose there are two ways to reach a certain city:
- Fare of \(5\) yen, travel time of \(2\) minutes
- Fare of \(2\) yen, travel time of \(4\) minutes
The former is faster, but leaves less budget remaining. Depending on the fares ahead, it might be possible to reach the destination only via the latter.
In other words, instead of only keeping the movement with the shortest time, we need to maintain the minimum time for each amount of fare spent. Trying to enumerate all possible paths and train choices is also impractical due to the extremely large number of candidates.
Utilizing the Monotonic Increase of Fare
The original railway network contains cycles, meaning cities can be visited multiple times. However, since the fare of each train is at least \(1\), the total fare spent strictly increases whenever a train is taken.
Therefore, if we define the state as (fare spent, current city), the fare at the transition destination is always strictly greater than at the transition source.
Due to this property, we only need to update the DP in increasing order of fare spent, and algorithms like Dijkstra’s algorithm are not necessary.
Algorithm
1. Register Travel Options as Edges
For each railway line, treat the two types of travel as separate edges:
- Local train: fare \(A_i\), travel time \(S_i\)
- Express train: fare \(B_i\), travel time \(T_i\)
Register both as bidirectional edges. Trains with a fare exceeding \(C\) can never be used, so there is no need to register them.
2. Define the DP Table
Let \(dp[c][v]\) be the following value:
The minimum travel time to travel from city \(1\) to city \(v\) using exactly \(c\) yen of fare for one person.
The value for unreachable states is set to \(\mathrm{INF}\).
The initial state is \(dp[0][1]=0\), and all others are \(\mathrm{INF}\). Note that if cities are \(0\)-indexed in the code, the initial state is dp[0][0] = 0.
3. Transitions in Increasing Order of Fare
Process the states for each city \(v\) in the order of \(c=0,1,\ldots,C\).
When \(dp[c][v]\) is reachable and there is a train from city \(v\) to city \(u\) with fare \(a\) and travel time \(t\), if \(c+a \leq C\), perform the following update:
\(dp[c+a][u] \leftarrow \min\bigl(dp[c+a][u],\ dp[c][v]+t\bigr)\)
Since \(a \geq 1\), the transition destination is always a state processed later.
Furthermore, any movement reaching a state with fare \(c\) must transition from a state with a fare strictly smaller than \(c\) at the last step. Because all of those states have already been processed earlier, the shortest time is correctly found in this order.
4. Find the Answer
Since it is not necessary to spend the entire budget, the answer is \(\min_{0 \leq c \leq C} dp[c][N]\).
If all values are \(\mathrm{INF}\), there is no way to reach the destination within budget, so output -1.
Complexity
Let \(C=\lfloor K/2 \rfloor\). At most \(4\) edges are registered for each railway line, so the number of edges is \(O(M)\).
- Time complexity: \(O((C+1)(N+M))\)
- Space complexity: \(O((C+1)N+M)\)
For each fare, all cities and their incident edges are inspected. Space is primarily used for the DP table and adjacency list.
Implementation Notes
Use 64-bit integers for travel time
Since a single train ride can take up to \(10^9\) minutes, the total time may exceed the 32-bit integer range. In the code,long longis used.Consider both local and express trains
An express train is not necessarily faster, nor is a local train necessarily cheaper. Do not make assumptions based on names; register each as an independent travel option.Do not transition from unreachable states
Skip processing ifdp[cost][v] == INF.Place the fare loop as the outer loop
Processing states in increasing order of fare is crucial for the correctness of this DP.Cases like \(K=0\) or \(K=1\) can be handled as-is
In this case, \(C=0\). Since all fares are positive, no trains can be taken, making city \(N\) unreachable, so-1is output.Source Code
#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;
}
This editorial was generated by gpt-6-astra-medium.
posted:
last update: