LeetCode 787. Cheapest Flights Within K Stops 题解题目描述有n个城市通过一些航班连接。给你一个数组flights其中flights[i] [fromi, toi, pricei]表示从fromi到toi的航班价格为pricei。现在给定所有的城市和航班以及出发城市src和目的地dst你的任务是找到从src到dst最多经过k站中转的最便宜的价格。 如果没有这样的路线则输出 -1。示例 1输入n 3, flights [[0,1,100],[1,2,100],[0,2,500]], src 0, dst 2, k 1 输出200 解释从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200路线是 0-1-2。示例 2输入n 3, flights [[0,1,100],[1,2,100],[0,2,500]], src 0, dst 2, k 0 输出500 解释从城市 0 到城市 2 没有中转的最便宜价格是 500。解题思路使用广度优先搜索BFS结合动态规划记录每个城市的最低价格使用队列进行层序遍历每层代表一个中转次数最多遍历 k1 层包括起点代码实现from collections import defaultdict, deque def findCheapestPrice(n, flights, src, dst, k): # 构建邻接表 graph defaultdict(list) for u, v, price in flights: graph[u].append((v, price)) # 记录到达每个城市的最低价格 prices [float(inf)] * n prices[src] 0 # 队列(城市, 当前价格, 剩余中转次数) queue deque([(src, 0, k 1)]) # k1 次飞行 while queue: city, cost, stops queue.popleft() if stops 0: continue if city dst: continue for neighbor, price in graph[city]: new_cost cost price if new_cost prices[neighbor] and stops 0: prices[neighbor] new_cost queue.append((neighbor, new_cost, stops - 1)) return prices[dst] if prices[dst] ! float(inf) else -1复杂度分析时间复杂度O(E × K)其中 E 是航班数量K 是最大中转次数空间复杂度O(V E)其中 V 是城市数量优化优先队列Dijkstra 算法import heapq from collections import defaultdict def findCheapestPrice(n, flights, src, dst, k): # 构建邻接表 graph defaultdict(list) for u, v, price in flights: graph[u].append((v, price)) # 优先队列(当前价格, 城市, 剩余中转次数) heap [(0, src, k 1)] # 记录到达每个城市的最低价格和剩余中转次数 visited {} while heap: cost, city, stops heapq.heappop(heap) if city dst: return cost if stops 0: continue # 如果已经访问过且价格更高跳过 if city in visited and visited[city] stops: continue visited[city] stops for neighbor, price in graph[city]: heapq.heappush(heap, (cost price, neighbor, stops - 1)) return -1测试案例# 测试案例 1 assert findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1) 200 # 测试案例 2 assert findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 0) 500 # 测试案例 3 assert findCheapestPrice(4, [[0,1,1],[0,2,5],[1,2,1],[2,3,1]], 0, 3, 1) 6总结本题是图论中的最短路径问题。关键点BFS 层序遍历控制中转次数动态规划记录最低价格优先队列优化通过本题可以深入理解图的遍历和最短路径算法。
LeetCode 787. Cheapest Flights Within K Stops 题解
LeetCode 787. Cheapest Flights Within K Stops 题解题目描述有n个城市通过一些航班连接。给你一个数组flights其中flights[i] [fromi, toi, pricei]表示从fromi到toi的航班价格为pricei。现在给定所有的城市和航班以及出发城市src和目的地dst你的任务是找到从src到dst最多经过k站中转的最便宜的价格。 如果没有这样的路线则输出 -1。示例 1输入n 3, flights [[0,1,100],[1,2,100],[0,2,500]], src 0, dst 2, k 1 输出200 解释从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200路线是 0-1-2。示例 2输入n 3, flights [[0,1,100],[1,2,100],[0,2,500]], src 0, dst 2, k 0 输出500 解释从城市 0 到城市 2 没有中转的最便宜价格是 500。解题思路使用广度优先搜索BFS结合动态规划记录每个城市的最低价格使用队列进行层序遍历每层代表一个中转次数最多遍历 k1 层包括起点代码实现from collections import defaultdict, deque def findCheapestPrice(n, flights, src, dst, k): # 构建邻接表 graph defaultdict(list) for u, v, price in flights: graph[u].append((v, price)) # 记录到达每个城市的最低价格 prices [float(inf)] * n prices[src] 0 # 队列(城市, 当前价格, 剩余中转次数) queue deque([(src, 0, k 1)]) # k1 次飞行 while queue: city, cost, stops queue.popleft() if stops 0: continue if city dst: continue for neighbor, price in graph[city]: new_cost cost price if new_cost prices[neighbor] and stops 0: prices[neighbor] new_cost queue.append((neighbor, new_cost, stops - 1)) return prices[dst] if prices[dst] ! float(inf) else -1复杂度分析时间复杂度O(E × K)其中 E 是航班数量K 是最大中转次数空间复杂度O(V E)其中 V 是城市数量优化优先队列Dijkstra 算法import heapq from collections import defaultdict def findCheapestPrice(n, flights, src, dst, k): # 构建邻接表 graph defaultdict(list) for u, v, price in flights: graph[u].append((v, price)) # 优先队列(当前价格, 城市, 剩余中转次数) heap [(0, src, k 1)] # 记录到达每个城市的最低价格和剩余中转次数 visited {} while heap: cost, city, stops heapq.heappop(heap) if city dst: return cost if stops 0: continue # 如果已经访问过且价格更高跳过 if city in visited and visited[city] stops: continue visited[city] stops for neighbor, price in graph[city]: heapq.heappush(heap, (cost price, neighbor, stops - 1)) return -1测试案例# 测试案例 1 assert findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1) 200 # 测试案例 2 assert findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 0) 500 # 测试案例 3 assert findCheapestPrice(4, [[0,1,1],[0,2,5],[1,2,1],[2,3,1]], 0, 3, 1) 6总结本题是图论中的最短路径问题。关键点BFS 层序遍历控制中转次数动态规划记录最低价格优先队列优化通过本题可以深入理解图的遍历和最短路径算法。
