leetcode787_go_K站中转内最便宜的航班

题目

有 n 个城市通过一些航班连接。给你一个数组 flights ，

其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，

使得从 src 到 dst 的价格最便宜，并返回该价格。如果不存在这样的路线，则输出 -1。

示例 1：输入: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 1 输出: 200

解释: 城市航班图如下

从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。

示例 2：输入: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 0 输出: 500

解释: 城市航班图如下

从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。

提示：1 <= n <= 100

0 <= flights.length <= (n * (n - 1) / 2)

flights[i].length == 3

0 <= fromi, toi < n

fromi != toi

1 <= pricei <= 104

航班没有重复，且不存在自环

0 <= src, dst, k < n

src != dst

解题思路分析

1、动态规划-二维；时间复杂度O(n^2)，空间复杂度O(n^2)

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
   maxValue := math.MaxInt32 / 10
   dp := make([][]int, k+2) // dp[i][j] => 经过i次航班到j地需要的最少花费（k次中转需要k+1次航班）
   for i := 0; i <= k+1; i++ {
      dp[i] = make([]int, n)
      for j := 0; j < n; j++ {
         dp[i][j] = maxValue
      }
   }
   dp[0][src] = 0 // 到开始地为0
   for i := 1; i <= k+1; i++ {
      for j := 0; j < len(flights); j++ {
         a, b, c := flights[j][0], flights[j][1], flights[j][2] // a=>b c
         dp[i][b] = min(dp[i][b], dp[i-1][a]+c)
      }
   }
   res := maxValue
   for i := 1; i <= k+1; i++ {
      res = min(res, dp[i][dst])
   }
   if res == maxValue {
      return -1
   }
   return res
}

func min(a, b int) int {
   if a > b {
      return b
   }
   return a
}

2、动态规划-一维；时间复杂度O(n^2)，空间复杂度O(n)

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
   maxValue := math.MaxInt32 / 10
   dp := make([]int, n) // dp[i] => 到j地需要的最少花费（k次中转需要k+1次航班）
   for i := 0; i < n; i++ {
      dp[i] = maxValue
   }
   dp[src] = 0 // 到开始地为0
   res := maxValue
   for i := 1; i <= k+1; i++ {
      temp := make([]int, n)
      for j := 0; j < n; j++ {
         temp[j] = maxValue
      }
      for j := 0; j < len(flights); j++ {
         a, b, c := flights[j][0], flights[j][1], flights[j][2] // a=>b c
         temp[b] = min(temp[b], dp[a]+c)

      }
      res = min(res, temp[dst])
      dp = temp
   }
   if res == maxValue {
      return -1
   }
   return res
}

func min(a, b int) int {
   if a > b {
      return b
   }
   return a
}

3、广度优先搜索；时间复杂度O(n^2)，空间复杂度O(n)

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
   maxValue := math.MaxInt32 / 10
   prices := make([]int, n)
   arr := make([][][2]int, n)
   for i := 0; i < n; i++ {
      prices[i] = maxValue
   }
   prices[src] = 0
   for i := 0; i < len(flights); i++ {
      a, b, c := flights[i][0], flights[i][1], flights[i][2] // a=>b c
      arr[a] = append(arr[a], [2]int{b, c})
   }
   queue := make([][3]int, 0)
   queue = append(queue, [3]int{1, src, prices[src]}) // 次数，起点，价格
   for len(queue) > 0 {
      node := queue[0]
      queue = queue[1:]
      if node[0] > k+1 { // 大于k+1次退出
         break
      }
      cur, value := node[1], node[2]
      for i := 0; i < len(arr[cur]); i++ {
         b, c := arr[cur][i][0], arr[cur][i][1]
         if prices[b] > c+value {
            prices[b] = c + value
            queue = append(queue, [3]int{node[0] + 1, b, prices[b]})
         }
      }
   }
   if prices[dst] == maxValue {
      return -1
   }
   return prices[dst]
}

func min(a, b int) int {
   if a > b {
      return b
   }
   return a
}

4、Bellman-Ford；时间复杂度O(n^2)，空间复杂度O(n)

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
   maxValue := math.MaxInt32 / 10
   dis := make([]int, n)
   for i := 0; i < n; i++ {
      dis[i] = maxValue
   }
   dis[src] = 0 // 到开始地为0
   for i := 1; i <= k+1; i++ {
      temp := make([]int, n)
      copy(temp, dis)
      for j := 0; j < len(flights); j++ {
         a, b, c := flights[j][0], flights[j][1], flights[j][2] // a=>b c
         temp[b] = min(temp[b], dis[a]+c)
      }
      dis = temp
   }
   if dis[dst] == maxValue {
      return -1
   }
   return dis[dst]
}

func min(a, b int) int {
   if a > b {
      return b
   }
   return a
}