787. Cheapest Flights Within K Stops
有n个city，要从src飞到dst、k代表你能转机几次
给一个array flights里面有三个元素[from, to, price]
代表飞机的起点、终点以及价钱
请问你最少要花多少钱才能从src到dst
思路 :
第一个想法觉得是最短路径问题的变形，想用Dijkstra's Algorithm
不过想不太出来
后来决定用queue+BST来做这题
从src开始去遍历每一次能到达的city
queue放这一轮所有能抵达且cost比上一轮低的city
每次去纪录有没有更小的成本，并记录下来
最后就可以找到答案了
golang code :
type connect struct {
city int
cost int
}
func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
minprice := math.MaxInt
cost := make([]int, n)
for i := 0; i < n; i++ {
cost[i] = math.MaxInt
}
rec := make([][]int, n)
for _, val := range flights {
rec[val[0]] = append(rec[val[0]], val[1]+val[2]*1000)
}
queue := make([]connect, 1)
queue[0] = connect{src, 0}
cost[src] = 0
cnt := 1
for k > -1 && len(queue) > 0 {
k

送我模型

大师

吃屎

大师

大师