Leetcode--K 站中转内最便宜的航班

K 站中转内最便宜的航班

有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线，则输出 -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，如图中蓝色所示。
提示：

n 范围是 [1, 100]，城市标签从 0 到 n - 1.
航班数量范围是 [0, n * (n - 1) / 2].
每个航班的格式 (src, dst, price).
每个航班的价格范围是 [1, 10000].
k 范围是 [0, n - 1].
航班没有重复，且不存在环路

动态规划（Dynamic Programming）

状态转移方程：

ans = min(ans, costs[k] + prices[k][dst])
​其中costs[k]表示到达位置k时的最小花费，prices[k][dst]表示从k到达dst的航班价格。

Python代码：

class Solution(object):def findCheapestPrice(self, n, flights, src, dst, K):""":type n: int:type flights: List[List[int]]:type src: int:type dst: int:type K: int:rtype: int"""INF = 0x7FFFFFFFprices = collections.defaultdict(lambda: collections.defaultdict(int)) #内置collection得到数组for s, t, p in flights:prices[s][t] = pans = prices[src][dst] or INF     #从src到dst的pricesqueue = [src]							#src的队列列表costs = {src : 0}					#费用的字典 key：src，value：数字for x in range(K + 1):nset = set()							#一个集合for loc in queue:                  #在当前的位置                                ans = min(ans, costs[loc] + (prices[loc][dst] or INF))for next in prices[loc]:              #下一段转的航班需要花费的费用costs[next] = min(costs.get(next, INF), costs[loc] + (prices[loc][next] or INF))nset.add(next)  			   #next为prices的一维数组，加入集合当中queue = list(nset)			#最后我们可以得到一个队列，存着每一个出发点，也就是航班return ans if ans < INF else -1        

但是提交会报错。。。。不知道为啥，再看看

另一种DP的思路：

用一个二维的dp数组，dp[i][j]表示在不超过i次转机的情况下，从j到达dst的最少费用。$dp[i][j]=min(dp[i-1][k]+Pk->jPk->j)$。
（从自己到自己为0，Pk−>k=0，若是没有这个线路则，Pk−>j=infPk−>k=0，若是没有这个线路则，Pk−>j=inf）

class Solution(object):def findCheapestPrice(self, n, flights, src, dst, K):""":type n: int:type flights: List[List[int]]:type src: int:type dst: int:type K: int:rtype: int176ms dp"""import collections# 记录同一个终点的不同起点和价格flights_dict_end = collections.defaultdict(list)for flight in flights:flights_dict_end[flight[1]].append([flight[0], flight[2]])# 用来记录各种情况，n个站点，还剩K次，到达目的地最少价格dp = [[float('inf') for i in range(n)] for i in range(K + 1)]# 初始化能直达的for i in flights_dict_end[dst]:dp[0][i[0]] = i[1]# 反向推回去for k in range(1, K + 1):for pos in range(n):for before in flights_dict_end[pos]:dp[k][before[0]] = min(dp[k][before[0]], dp[k-1][pos] + before[1])dp[k][pos] = min(dp[k][pos], dp[k-1][pos])ans = dp[K][src]return ans if ans != float('inf') else -1