A courier travels a weighted directed network of n waypoints (numbered 0 to n-1) connected by one-way legs, each with a positive integer toll. The courier holds k free-leg vouchers: on up to k of the legs used along the route, the toll may be waived (treated as 0). Vouchers are optional and each covers one traversal of one leg.
Starting at waypoint 0, find the minimum total toll to reach waypoint n-1, using at most k vouchers optimally. If waypoint n-1 cannot be reached, report that it is impossible.
Line 1: two integers n and m.
Each of the next m lines: three integers u v w, a one-way leg from u to v with toll w.
Final line: a single integer k, the number of free-leg vouchers.
A single integer: the minimum total toll from waypoint 0 to waypoint n-1 using at most k vouchers, or -1 if unreachable.
Example 1
Input
4 3 0 1 100 1 2 1 2 3 100 1
Expected
101
Explanation
The only route 0->1->2->3 has tolls 100,1,100. Waiving one leg is best on a 100 leg, leaving 1+100=101.
Example 2
Input
4 3 0 1 100 1 2 1 2 3 100 2
Expected
1
Explanation
With two vouchers, both 100 tolls are waived, leaving only the toll of 1: total 1.
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 →