Cheapest Flights Within K Stops

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates a flight from city fromi to city toi with cost pricei.

Given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

A stop is an intermediate city you land in. A direct flight (no intermediate cities) has 0 stops.

---

Example 1

        100
  0 ---------> 1
  |            |
  |500         |100
  v            v
  3 <--------- 2
        100

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation: The cheapest route with at most 1 stop is 0 -> 1 -> 3 (cost 700). Direct 0 -> 3 does not exist; going via 2 needs 2 stops.

Example 2

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation: 0 -> 1 -> 2 costs 200 (1 stop); 0 -> 2 costs 500 (0 stops). 200 is cheaper.

---

Constraints

• 1 <= n <= 100
• 0 <= flights.length <= (n * (n - 1) / 2)
• flights[i].length == 3
• 0 <= fromi, toi < n
• fromi != toi
• 1 <= pricei <= 10^4
• There will not be any multiple flights between two cities
• 0 <= src, dst, n - 1
• src != dst
• 0 <= k < n