GraphBellman-FordShortest PathDynamic Programming
There are n cities and directed flights (from, to, price). Find the cheapest price to travel from city src to city dst using at most k stops (a stop is an intermediate city, so a route with k stops uses at most k + 1 flights). Print -1 if no such route exists.
Input
Line 1: n and m. Next m lines: from to price. Last line: src, dst and k.
Output
Print the cheapest price, or -1.
Constraints
2 <= n <= 100 0 <= m <= n * (n - 1) / 2 0 <= k < n 1 <= price <= 10^4
Example 1
Input
4 5 0 1 100 1 2 100 2 0 100 1 3 600 2 3 200 0 3 1
Output
700
With 1 stop the cheapest route 0 -> 1 -> 3 costs 700.