Loading...
Loading...
Loading...
Riya is flying home from college for Diwali. There are n cities, numbered 1 to n, and m one-way flights. Each flight has a fixed ticket price.
She starts in city s and wants to reach city t. A stop is a city where she lands and changes to another flight. She does not want more than k stops, so a route can use at most k + 1 flights.
Print the smallest total price of such a route. If she is already at home (s equals t), print 0. If no route with at most k stops exists, print -1.
Example 1
Input
4 5 1 2 100 2 3 100 2 4 600 3 4 200 1 4 900 1 4 1
Output
700
With one stop, the routes are the direct flight for 900 and 1 → 2 → 4 for 700. The route 1 → 2 → 3 → 4 costs only 400, but it has two stops. The answer is 700.
Example 2
Input
3 2 1 2 50 2 3 50 1 3 0
Output
-1
With 0 stops only a direct flight works, and there is no flight from city 1 to city 3.
Try the problem first. Open one hint at a time.
Count flights instead of stops: at most k stops means at most k + 1 flights.
Keep cost[c]: the cheapest price to reach city c using the flights taken so far. At the start only cost[s] is 0.
Do exactly k + 1 rounds. In each round, try every flight once and see if it gives a cheaper price at its end city.
Inside a round, read prices from a copy made before the round started. Otherwise one round can chain several flights together and break the stop limit.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor