Distance or Time
National Olympiad — National round
Submission name: courier.cpp
Problem summary
Find the fastest route in a directed road network, starting at intersection 0 with speed 70. A road with a positive speed sign sets the current speed; a road with sign 0 preserves it. Road travel time equals length divided by the current speed after applying its sign.
Input
N M S; then M lines A B V L. Vertices are 0…N−1; S is the destination.
Output
The visited intersections in order from 0 to S. The optimal route is unique.
Constraints
2 ≤ N ≤ 150; 0 ≤ V ≤ 500; 1 ≤ L ≤ 500; at most one directed road for a given ordered pair.
Worked example
An independently prepared example for this explanation.
Input
3 3 2 0 1 100 100 1 2 0 100 0 2 50 150
Output
0 1 2
Solution analysis
- A vertex alone is not enough: arriving with different speeds changes the cost of roads without signs.
- Use states (intersection, speed), with speeds 1…500. Start at (0,70).
- For a road (u,V,L), use newSpeed = V if V>0, otherwise the state’s current speed. Relax by L/newSpeed.
- Run Dijkstra over states. Pick the cheapest state at S, then follow stored parent states to reconstruct the route.
Why it works
The expanded graph records all information relevant to future travel times. Each legal route maps to a state path with the same time, and all state transitions have positive costs. Dijkstra therefore finds the fastest route.
Watch out. Two visits to the same intersection may both matter. Use floating-point travel times; never truncate length/speed by integer division.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<queue>
#include<tuple>
#include<functional>
#include<algorithm>
#include<limits>
using namespace std;
struct Road{
int to,sign,length;
};
int main(){
int n,m,target;
cin>>n>>m>>target;
vector<vector<Road>>g(n);
for(int i=0;i<m;++i){
int a,b,v,l;
cin>>a>>b>>v>>l;
g[a].push_back({b,v,l});
}
const double INF=numeric_limits<double>::infinity();
vector<vector<double>>d(n,vector<double>(501,INF));
vector<vector<pair<int,int>>>parent(n,vector<pair<int,int>>(501,{-1,-1}));
using State=tuple<double,int,int>; // time, intersection, current speed
priority_queue<State,vector<State>,greater<State>>q;
d[0][70]=0;
q.push({0,0,70});
while(!q.empty()){
auto[time,v,speed]=q.top();
q.pop();
if(time!=d[v][speed]){
continue;
}
for(auto e:g[v]){
int ns=e.sign?e.sign:speed;
double nt=time+(double)e.length/ns;
if(nt<d[e.to][ns]){
d[e.to][ns]=nt;
parent[e.to][ns]={v,speed};
q.push({nt,e.to,ns});
}
}
}
int speed=1;
for(int s=2;s<=500;++s){
if(d[target][s]<d[target][speed]){
speed=s;
}
}
if(d[target][speed]==INF){
return 0;
}
vector<int>path;
int v=target;
while(v!=-1){
path.push_back(v);
auto p=parent[v][speed];
v=p.first;
speed=p.second;
}
reverse(path.begin(),path.end());
for(int i=0;i<(int)path.size();++i){
cout<<(i?" ":"")<<path[i];
}
cout<<'\n';
}