## 题目

There are `n`

cities connected by `m`

flights. Each flight starts from city `u`

and arrives at `v`

with a price `w`

.

Now given all the cities and flights, together with starting city `src`

and the destination `dst`

, your task is to find the cheapest price from `src`

to `dst`

with up to `k`

stops. If there is no such route, output `-1`

.

Example 1:

1 | Input: |

Example 2:

1 | Input: |

**Constraints:**

- The number of nodes
`n`

will be in range`[1, 100]`

, with nodes labeled from`0`

to`n - 1`

. - The size of
`flights`

will be in range`[0, n * (n - 1) / 2]`

. - The format of each flight will be
`(src, dst, price)`

. - The price of each flight will be in the range
`[1, 10000]`

. `k`

is in the range of`[0, n - 1]`

.- There will not be any duplicated flights or self cycles.

## 思路

BFS.

## 代码

1 | class Solution(object): |