难度：★★★★☆
类型：图
方法：深度优先搜索,动态规划
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
题目
有 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
提示：
n 范围是 [1, 100]，城市标签从 0 到 n - 1
航班数量范围是 [0, n * (n - 1) / 2]
每个航班的格式 (src, dst, price)
每个航班的价格范围是 [1, 10000]
k 范围是 [0, n - 1]
航班没有重复，且不存在自环
解答
方法1：深度优先搜索
城市与城市之间通过航班连接起来，直接构成了一张有向图，我们可以考虑用深度优先搜索的办法解决这类问题。
【建图】
首先根据题目中的输入把图建立起来，定义数组fares，维度为n×n，其中n即为城市个数，fares[i][j]表示从城市i到城市j的航班费用。
【其他变量】
定义结果变量res，用于保存总花费，初始化为无穷；
定义足迹数组visited，列表长度为n，用来避免走回头路，除了起点城市外初始化为False；
【深度优先搜索】
定义深度优先搜索函数dfs，函数的输入有三个：
1.当前城市current_city，
2.到达当前城市的花费cost，
3.已经使用的路线数transit_times，
函数没有返回值，函数实现的功能是对从src城市到dst城市的路线进行寻迹。
在函数内部，首先判断特殊情况，减少计算开销：
如果倒班次数transit_times已经用完，或者开销已经超过了当前开销res，直接返回；
如果当前城市即为终点城市，更新总路费res；
其他情况下，寻找当前城市可以到达的城市，并且要求这个城市没有到过，然后以该城市为当前城市，递归调用进行路径搜索，这里要注意当前路费cost和倒班次数transit_times的更新。
最后返回res即可，如果res为无穷，说明无法到达目标城市。
class Solution:
def findCheapestPrice(self, n: int, flights, src: int, dst: int, K: int) -> int:
# 制作起点->终点路线价格对应关系表fares，fares[i][j]表示从i城市到j城市的票价
fares = [[None] * n for _ in range(n)]
for city1, city2, price in flights:
fares[city1][city2] = price
visited = [True if i == src else False for i in range(n)] # 足迹列表
res = float('inf') # 最终票价
def dfs(current_city, cost, transmit_times):
nonlocal res, visited # 局部变量全局化
if transmit_times < 0 or cost > res: # 跳出条件
return
if current_city == dst: # 到达终点，更新总票价
res = min(res, cost)
return
for next_city in range(n):
if fares[current_city][next_city] is not None and not visited[next_city]: # 找到所有没有去过并且存在路线的下一个城市
visited[next_city] = True # 更新足迹列表
dfs(next_city, cost + fares[current_city][next_city], transmit_times - 1) # 深度优先搜索从下一个城市开始
visited[next_city] = False # 还原足迹列表
dfs(src, 0, K+1)
return res if res != float('inf') else -1
解法2：动态规划
接下来介绍一种更加高效的计算方式，即使用动态规划实现。
【数组定义】
定义数组dp，维度为(K+1)×n，dp[k][i]表示经过k次中转到达i城市的最小花费。
【初始情况】
首先把起始城市src可以直接到达的城市d填充在dp数组中，即dp[0][src]=price，这些城市可以不经过中转到达的，其他位置初始化为无穷。
【递推公式】
中转次数从1开始增加，对于图中的所有边(起点s, 终点d, 票价p)，更新当前中转次数k下到达城市d的最少总票价。经过k次中转到达城市d的最少总票价dp[k][d]，取决于三项内容：
当前记录中的dp[k][d]；
经过k-1次中转到达城市d的最少总票价dp[k-1][d]；
经过k-1次中转到达城市s的最少总票价dp[k-1][s]与从s到d的票价p的和；
选择三项内容最小值作为当前位置dp[k][d]的结果。
【返回值】
最终返回dp[K][dst]即可，同样考虑是否可到达。
class Solution(object):
def findCheapestPrice(self, n, flights, src, dst, K):
dp = [[float('inf') for _ in range(n)] for _ in range(K+1)]
for s, d, p in flights:
if s == src:
dp[0][d] = p
for k in range(1, K+1):
for s, d, p in flights:
dp[k][d] = min(dp[k][d], dp[k-1][d], dp[k-1][s]+p)
return dp[K][dst] if dp[K][dst] != float('inf') else -1
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
