787. Cheapest Flights Within K Stops

Stanislav Gumeniuk включен в Leetcode Leetcode-Problem

2020-06-15 266 слов 2 минуты

Содержание

Условие

Есть m городов , соединённых m рейсами. Каждый рейс стартует из города u и прибывает в город v и имеет стоимость w.

Даны все города и рейсы, связывающие их. Наша задача найти самый дешевый путь из src в dst с неболее чем K пересадками. Если такого пути нет – вернуть -1.

пример 1

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

пример 2

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

Ограничения:

Дублирующих полетов и полетов петлей не будет.

Решение

DFS

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
}