Условие
Есть m городов , соединённых m рейсами. Каждый рейс стартует из города u и прибывает в город v и имеет стоимость w.
Даны все города и рейсы, связывающие их. Наша задача найти самый дешевый путь из src в dst с неболее чем K пересадками. Если такого пути нет – вернуть -1.
пример 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
|
пример 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
|
Ограничения:
- Дублирующих полетов и полетов петлей не будет.
Решение
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[1]] ; !ok {
f[c[1]] = make(map[int]int, 1)
}
f[c[1]][c[0]] = c[2]
}
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
}
|