KBLTRNS
Time limit2sMemory limit512 MB
Given several routes, each with a time and a price, print the smallest time among the routes that reach the destination within the 12 hour limit.
- Level
Easy2 of 10
- Topics
- Implementation, Array, Brute force
- Solved
- No attempts yet
Problem
Kabul is a populated city. However, public transportation has not grown at this stage. As a result, people in the morning and evening have many problems getting to their destinations. The good thing about this city is that you can reach your destination using different routes. Every route has an associated time and price.
One day, Toryalai has an urgent job to complete. He is in a hurry and wants to get to his destination as soon as possible. Your job is to help Toryalai reach his destination in the minimum amount of time. Toryalai can go to his destination using many routes, and routes can be formed by different intersections. Help him find the best route to his destination from the provided routes.
Note: Toryalai cannot switch among routes.
Input
The first line is the number of test cases. The second line (R) contains the number of routes Toryalai can use to reach the destination. Then R lines contain the routes' associated times and prices. The start point is A and the destination is D. The maximum time Toryalai has is 12 hours, and the associated time for every route intersection is given to you in minutes.
Note:
There is no route exceeding the maximum time.
Every route reaches the destination.
Output
The time when Toryalai selects the route with the minimum associated time.