Contents

# Problem

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 2 3 4 5 `````` ``````Example 1: Input: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 1 Output: 200 ``````

## example 2

 ``````1 2 3 4 5 `````` ``````Example 2: Input: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 0 Output: 500 ``````

## 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.

# Solution

## DFS

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 `````` ``````func findCheapestPrice(n int, flights [][]int, src int, dst int, K int) int { a := make([]int, n) a[src] = 0 f:=make(map[int]map[int]int, 0) for idx := range flights { c := flights[idx] if _, ok := f[c] ; !ok { f[c] = make(map[int]int, 1) } f[c][c] = c } min := -1 return helper2(f, dst, 0, K, src, map[int]int{}, &min) } func helper2(flights map[int]map[int]int, c, sum,maxk, dst int, v map[int]int, min *int) int{ if len(v)-1>maxk { return -1 } if c == dst { return sum } if *min != -1 && sum > *min { return -1 } minsum := -1 for idx:= range flights[c] { if _, ok := v[idx]; ok { continue } tmpsum:=sum+flights[c][idx] v[idx] = 1 res :=helper2(flights, idx, tmpsum,maxk, dst, v,min) delete(v, idx) if res!=-1 && (minsum == -1 || minsum>res) { minsum = res } } if minsum!= -1 && (*min == -1 || minsum < *min) { *min = minsum } return minsum } ``````