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

// @Title: K 站中转内最便宜的航班 (Cheapest Flights Within K Stops)
// @Author: 15816537946@163.com
// @Date: 2019-09-09 23:18:15
// @Runtime: 16 ms
// @Memory: 5.8 MB
import "container/list"

const MAX_INT = int(^uint(0) >> 1)
func findCheapestPrice(n int, flights [][]int, src int, dst int, K int) int {
    ret := MAX_INT
    graph := make([][][]int,n)
    for _, flight := range flights {
        graph[flight[0]] = append(graph[flight[0]], flight[1:])
    }
    queue := list.New()
    queue.PushBack([]int{src,0})
    level := 0
    for queue.Len() != 0 && level <= K+1 {
        size := queue.Len()
        for i := 0; i< size; i++ {
            e := queue.Front()
            queue.Remove(e)
            curr := e.Value.([]int)
            if curr[0] == dst && ret > curr[1] {
                ret = curr[1]
            }
            
            for _, edge:= range graph[curr[0]] {
                if tempCost := curr[1] + edge[1];tempCost < ret {
                    queue.PushBack([]int{edge[0],tempCost})
                }
            }
        }
        level++
    }
    if ret == MAX_INT {
        return -1
    } else {
        return ret
    }
}