You are given n cities, numbered from $0$ to n $- 1$ connected by several flights. You are also given an array flights, where each flight is represented as flights[i] $= [{from}_i, {to}_i, {price}_i]$ meaning there is a direct flight from city $fromᵢ$ to city $toᵢ$ with a cost of $priceᵢ$.

You are also given three integers:

• src: The starting city.

• dst: The destination city.

• k: The maximum number of stops allowed on the route (i.e., intermediate cities between src and dst).

Your task is to find the minimum possible cost to travel from src to dst using at most k stops (i.e., the route may contain up to k + 1 flights). If there is no valid route from src to dst that uses at most k stops, return $-1$.

Constraints:

• $2 \leq$ n $\leq$ $100$

• $0 \leq$ flights.length $\leq (n \times (n - 1) / 2)$

• flights[i].length $== 3$

• $0 \leq {from}_i$ , ${to}_i < n$

• ${from}_i \ne {to}_i$

• $1 \leq {price}_i \leq 10^4$

• There will not be any multiple flights between two cities.

• $0 \leq$ src, dst, k $< n$

• src $\ne$ dst

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.