手机网站关于我们,网络工程师是青春饭吗,腾讯广告推广怎么做,网络营销的主要方式题目
leetcode787. K 站中转内最便宜的航班
题目分析
给定一个城市图#xff0c;每个城市通过航班与其他城市相连。每个航班都有一个起点、终点和价格。你需要找到从起点城市 src 到终点城市 dst 的最便宜路径#xff0c;但这条路径最多只能经过 k 个中转站。你需要返回这…题目
leetcode787. K 站中转内最便宜的航班
题目分析
给定一个城市图每个城市通过航班与其他城市相连。每个航班都有一个起点、终点和价格。你需要找到从起点城市 src 到终点城市 dst 的最便宜路径但这条路径最多只能经过 k 个中转站。你需要返回这种路径的最低价格如果不存在这样的路径则返回 -1。
输入
n城市的数量 flights航班的列表每个航班用 [fromi, toi, pricei] 表示表示从城市 fromi 到城市 toi 的航班价格为 pricei src起点城市 dst终点城市 k最多经过的中转站数
输出
最便宜的价格如果没有满足条件的路径则输出 -1
思路分析
我看到这道题第一时间想的就是dijkstra算法因为我也不会别的算法。 对于k的限制我想到可以在优先队列中维护一个当前层级的变量当到达的层级大于k时就不再扩展了。
但是我没考虑到k的限制可能会导致最短路径无法达成并且由于dijkstra算法的性质其他路线也被直接丢弃了
于是我尝试不使用visited数组记录访问过的节点将每个节点的后继节点都加入队列中只有层级大于k时才会跳过。此时算法退化成了变体的广度优先搜索算法会搜索每一条在中转数在k内的路径。
但是当数据量大了之后显然这个算法会超时。
继续思考发现dijkstra算法找到的是最优路径但是其中转节点可能很多而真正的路径只可能在中转节点比最优路径少的路径里其他中转节点多于最优路径的路径完全可以剪枝因为他们的费用不可能更低。
按照这个思路只需要维护一个每个节点的最小中转数任何多于最小中转数的路径都可以剪枝因为对于每一个被剪枝的路径来说在其之前都已经有至少一条路径价格比它低的同时中转数还要小于它
代码
class Solution:def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) - int:# 建立邻接表maps[[] for _ in range(n)]for edge in flights:maps[edge[0]].append(edge[1:])#最小堆模拟优先队列,价格节点编号层级pq[(0,src,0)]#当前每个节点的中转数记录visit[n1]*nwhile pq:w,p,cheappop(pq)#过滤超过层级k的节点剪枝中转城市多余当前节点记录的点if cvisit[p] or ck1:continueif p dst:return w# 直接等就可以,比它大的到不了这一步visit[p]c# 将后继节点加入优先队列for point in maps[p]:heappush(pq,(w point[1],point[0],c1))return -1
提交
一直交刷成绩QAQ 2024/8/8
