There are n cities, numbered from 0 to n - 1. The list flights holds one-way flights [from, to, price].
Find the cheapest way to travel from the city src to the city dst with at most k stops in between. Return its total price. If there is no such trip, return -1.
Examples
Example 1:
Input: n = 5, flights = [[0,1,50],[1,2,50],[2,4,50],[0,3,200],[3,4,100]], src = 0, dst = 4, k = 1
Output: 300
Explanation: With at most 1 stop, the route 0 -> 3 -> 4 costs 200 + 100 = 300. The cheaper route 0 -> 1 -> 2 -> 4 needs 2 stops.
Example 2:
Input: n = 5, flights = [[0,1,50],[1,2,50],[2,4,50],[0,3,200],[3,4,100]], src = 0, dst = 4, k = 2
Output: 150
Explanation: With 2 stops, the route 0 -> 1 -> 2 -> 4 is allowed. It costs 50 + 50 + 50 = 150.
Example 3:
Input: n = 5, flights = [[0,1,50],[1,2,50],[2,4,50],[0,3,200],[3,4,100]], src = 0, dst = 4, k = 0
Output: -1
Explanation: With no stops you need a direct flight from city 0 to city 4. There is none.