Fastest Journey within a Budget
Autumn Tournament (2016)
Submission name: traveling.cpp
Problem summary
Undirected bus routes have positive travel times and ticket costs; parallel routes are allowed. Travel from town1 to townN using at most S money, minimizing total travel time. Print−1 if impossible.
Input
S N M, then M lines v w time cost.
Output
The minimum travel time, or−1.
Constraints
1≤S≤2000; 1≤N≤3000; 1≤M≤5000; each time and cost is1…100.
Worked example
Original statement sample.
Input
7 4 6 1 2 2 5 1 3 2 2 1 4 7 3 2 3 1 2 2 4 2 3 3 4 5 2
Output
5
Solution analysis
- A town alone is not a sufficient state: reaching it quickly but expensively can be worse than a slower cheap arrival. Define best[spent][town] as the least time among paths spending exactly spent. Initialize only best[0][1]=0.
- Process spent values in increasing order. Every ticket has positive cost, so transitions go to a strictly larger spent value. This is a DAG ordering of the expanded state graph. For every reachable state, relax all outgoing routes within the budget.
- Take the minimum best[spent][N] over0≤spent≤S. In the sample,1→3→2→4 costs2+2+3=7 and takes2+1+2=5, beating the direct seven-hour route. The positive-cost condition makes cycles harmless in the increasing-budget DP.
Why it works
Every expanded edge increases spent, so all predecessors of a state are processed before it. By induction, relaxing them computes its exact shortest travel time. Every legal journey appears as a path in this graph, and minimizing over all final expenditures enforces the at-most budget condition.
Watch out. Do not keep only one time per town. Costs must be positive for this DP order. Preserve parallel buses, as their time/cost trade-offs can differ. Include spent=0 so N=1 is handled.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
struct Bus{
int to;
int time;
int cost;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int budget,n,m;
cin>>budget>>n>>m;
vector<vector<Bus>>graph(n+1);
for(int i=0;i<m;i++){
int u,v,time,cost;
cin>>u>>v>>time>>cost;
graph[u].push_back({v,time,cost});
graph[v].push_back({u,time,cost});
}
const int infinity=1000000000;
vector<vector<int>>best(budget+1,vector<int>(n+1,infinity));
best[0][1]=0;
for(int spent=0;spent<=budget;spent++){
for(int town=1;town<=n;town++){
if(best[spent][town]==infinity){
continue;
}
for(Bus bus:graph[town]){
if(spent+bus.cost<=budget){
// Positive ticket costs make this a forward DAG transition.
int&next=best[spent+bus.cost][bus.to];
next=min(next,best[spent][town]+bus.time);
}
}
}
}
int answer=infinity;
for(int spent=0;spent<=budget;spent++){
answer=min(answer,best[spent][n]);
}
cout<<(answer==infinity?-1:answer)<<'\n';
}