An airline operates m one-way flights among n cities (numbered 0 to n-1). Each flight goes from one city to another for a positive integer fare.
A traveller wants to fly from city src to city dst using at most k layovers, where a layover is an intermediate city where the traveller changes flights. Using at most k layovers is exactly the same as taking at most k+1 flights in total. Find the minimum total fare of such a trip, or report that no valid trip exists.
Line 1: two integers n and m.
Each of the next m lines: three integers u v w, a one-way flight from city u to city v with fare w.
Final line: three integers src dst k.
A single integer: the minimum total fare using at most k layovers, or -1 if no such trip exists.
Example 1
Input
4 5 0 1 100 1 2 100 0 2 500 2 3 100 1 3 600 0 3 1
Expected
600
Explanation
With at most 1 layover (2 flights): 0->2->3 costs 600 and 0->1->3 costs 700. The 300-cost route 0->1->2->3 needs 2 layovers and is not allowed, so the answer is 600.
Example 2
Input
4 5 0 1 100 1 2 100 0 2 500 2 3 100 1 3 600 0 3 2
Expected
300
Explanation
With up to 2 layovers, 0->1->2->3 (three flights) is allowed and costs 100+100+100=300, cheaper than the two-flight options.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →