→ oin1104: 送我模型 02/23 18:53
推 ILoveErr: 大師 02/23 18:53
→ JIWP: 吃屎 02/23 18:53
推 sustainer123: 大師 02/23 18:55
→ PogChampLUL: 大師 02/23 18:55
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--
for cnt > 0 {
cnt--
now := queue[0]
queue = queue[1:]
for _, val := range rec[now.city] {
city := val % 1000
price := val / 1000
if city == dst {
if now.cost+price < minprice {
minprice = now.cost + price
}
continue
}
if price+now.cost < cost[city] {
cost[city] = price + now.cost
queue = append(queue, connect{city, cost[city]})
}
}
}
cnt = len(queue)
}
if minprice == math.MaxInt {
return -1
}
return minprice
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.133.158 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1708685584.A.84E.html