难度：★★★★☆
类型：图
方法：深度优先搜索,动态规划

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

题目

有 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解决方案，请移步力扣中等题解析