解题思路 状态定义， d p [ u ] [ v ] [ k ] dp[u][v][k] dp[u][v][k]代表从城市 u u u到达城市 v v v，最多经过 k k k个中转站得到的最小的距离。本题中，源城市确定，显然这里上面定义状态的第一维 u u u就不需要了，所以我们的状态 d p [ v ] [ k ] dp[v][k] dp[v][k]代表从城市 s r c src src到达

题目描述 有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。

ac code class Solution:def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:# k站中转，可以走k + 1次connect = defaultdict(dict) # 二维dictfor x, y, c in flights:co

有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不

题目描述： 有 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

Leetcode 787. K 站中转内最便宜的航班 题目 有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线，则输出 -1。 测试样例 示例 1： 输入: n = 3, edges =

有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如

787. K 站中转内最便宜的航班 - 力扣（LeetCode） 典型的dijkstra算法，几乎是固定优先级队列加上bfs（bfs求出的都是最大/最小）的思路了，这题多加了一个中转站的限制 不过我还是太年轻，代码并没有通过全部案例，第43个卡住了，主要问题是使用优先级队列的话，跳出循环的条件很难处理，k值和终点哪个作为判断依据暂时不明确。 class Solution {public: