Problem C
CDOT Pathfinder
The Colorado Department of Transportation wants to create a program to find the fastest route to a destination, using roadways. They’ve hired you to create a program that decides the quickest path to take. CDOT already has a program that can get a list of routes in-between each city, the distance of each route, as well as calculate each route’s average travel speed. Using this cartographic data from each possible route, your program must find the route at each leg that minimizes the trip time.
Input
The first line of input will be the total number of legs
required to reach the destination. There will always be at
least one, but no more than $25$ legs. The lines that follow are
grouped into pairs. Each pair corresponds to a city. The first
line of the pair contains one number: the number of possible
routes from the current city to the next one. The second line
in the pair contains two numbers for every route. The first
number for a route is the average speed given in miles per
hour, and the second number is the distance of the route, given
in miles. There will always be at least one route from one city
to the next, but no more than $25$. All numbers given are guaranteed
to be positive integers. Speed will never exceed $100$mph, and distance will never
exceed $500$ miles. No two
routes on the same leg will ever take the same amount of
time.
Note the Sample Input $1$ below matches the figure provided.
Output
Your program’s output should be a list of numbers representing which route should be taken at each leg to get the fastest possible trip (according to duration). Output your list as one number per line, with the top number representing the route to take at the first leg, the next number representing the route to take at the second leg, and so on. Routes should be indexed from one onwards, with one being the leftmost pair of values in the input of possible routes.
Sample Input 1 | Sample Output 1 |
---|---|
4 2 20 15 30 25 3 60 40 50 50 26 30 4 25 14 35 10 30 8 60 35 1 35 10 |
1 1 3 1 |
Sample Input 2 | Sample Output 2 |
---|---|
3 3 70 150 55 110 30 84 6 30 20 60 35 20 80 50 41 30 15 85 90 2 55 47 47 55 |
2 5 1 |