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

送我模型

大師

吃屎

大師

大師