| English | 简体中文 |

# 787. Cheapest Flights Within K Stops

## Description

There are `n`

cities connected by some number of flights. You are given an array `flights`

where `flights[i] = [from`

indicates that there is a flight from city _{i}, to_{i}, price_{i}]`from`

to city _{i}`to`

with cost _{i}`price`

._{i}

You are also 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`

.

**Example 1:**

Input:n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1Output:700Explanation:The graph is shown above. The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700. Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

**Example 2:**

Input:n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1Output:200Explanation:The graph is shown above. The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

**Example 3:**

Input:n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0Output:500Explanation:The graph is shown above. The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.

**Constraints:**

`1 <= n <= 100`

`0 <= flights.length <= (n * (n - 1) / 2)`

`flights[i].length == 3`

`0 <= from`

_{i}, to_{i}< n`from`

_{i}!= to_{i}`1 <= price`

_{i}<= 10^{4}- There will not be any multiple flights between two cities.
`0 <= src, dst, k < n`

`src != dst`