LeetCode 3651. 带传送的最小路径成本【分层最短路并查集优化 超详细解析】 文章前言今天解析一道 LeetCode 困难图论经典题3651.带传送的最小路径成本。本题区别于传统二维网格最短路新增了全局零成本传送机制暴力 Dijkstra 会因传送边数量爆炸直接超时。本题核心考点分层图最短路思想 Dijkstra 贪心性质 并查集批量松弛优化是非常经典的「图论优化进阶模板题」。本文从零推导解题思路、拆解超时原因、讲解核心优化原理附带可直接提交的完整代码、逐行注释、复杂度分析、案例推演、易错点总结适合进阶算法刷题、面试复盘。一、题目完整描述给定一个m x n的二维整数网格grid和整数k。起点左上角\(0, 0\)终点右下角\(m\-1, n\-1\)。支持两种移动方式1. 普通移动仅能向右 / 向下移动移动成本 目标单元格的数值不消耗传送次数。2. 传送移动最多k次从任意\(i,j\)传送到任意满足grid\[x\]\[y\] ≤ grid\[i\]\[j\]的\(x,y\)成本为0消耗1次传送次数。要求返回从起点到终点的最小总成本。题目约束关键2 ≤ m, n ≤ 80网格最大 80*806400 个节点0 ≤ grid\[i\]\[j\] ≤ 1e40 ≤ k ≤ 10传送次数极少分层核心依据示例演示示例1输入grid [[1,3,3],[2,5,4],[4,3,5]], k 2输出7最优路径正常移动到(1,1)成本7 → 零成本传送到终点(2,2)总代价7示例2输入grid [[1,2],[2,3],[3,4]], k 1输出9最优方案全程普通移动传送无法带来收益二、暴力思路与超时原因避坑重点2.1 基础思路分层 Dijkstra因为传送次数有限我们可以定义三维状态dist\[i\]\[j\]\[c\]使用c次传送到达\(i,j\)的最小成本最终答案min\(dist\[m\-1\]\[n\-1\]\[0\.\.\.k\]\)状态转移分为两种普通移动、传送移动。2.2 暴力写法致命问题普通移动仅2个方向完全无压力但传送是全局跳转每个状态都需要遍历整张网格所有满足grid\[x\]\[y\] ≤ grid\[i\]\[j\]的节点。状态总数80\*80\*11 70400单次传送最多遍历 6400 个格子总运算量4.5亿次Python 绝对超时。三、核心优化原理解题精髓3.1 Dijkstra 贪心核心性质Dijkstra 优先队列每次弹出当前代价最小的状态。传送代价为0一旦某个格子\(x,y\)在c\1层被更新过一次后续所有传送更新的代价一定更大或相等无需重复更新。结论每一层传送状态下每个格子仅需被传送更新一次3.2 并查集优化方案我们不需要每次遍历全网格而是预处理将所有格子按数值分桶相同数值的格子放在一个列表为每一个传送目标层c\1维护一个并查集并查集作用跳跃跳过已经被更新过的数值区间每次传送时批量更新所有未更新、且数值≤当前格子数值的所有格子更新后永久标记该数值已清空。最终将传送操作复杂度从O(N²)降为O(N) 均摊。四、完整可提交代码超详细注释严格遵循题目要求代码格式LeetCode 直接ACfromtypingimportListimportheapqclassSolution:defminCost(self,grid:List[List[int]],k:int)-int:m,nlen(grid),len(grid[0])# 找出网格最大值用于数值分桶与并查集初始化max_valmax(max(row)forrowingrid)# 1. 数值分桶将所有格子按数值分组# cells_by_val[v] 存储所有值为v的坐标cells_by_val[[]for_inrange(max_val1)]foriinrange(m):forjinrange(n):cells_by_val[grid[i][j]].append((i,j))# 2. 初始化三维距离数组 dist[i][j][使用传送次数]INFfloat(inf)# dist[m][n][k1]dist[[[INF]*(k1)for_inrange(n)]for_inrange(m)]dist[0][0][0]0# 优先队列(当前总代价, x, y, 已使用传送次数)heap[(0,0,0,0)]# 3. 并查集类用于批量跳过重扫数值classUnionFind:__slots__(father,)def__init__(self,size):self.fatherlist(range(size))deffind(self,x):# 路径压缩ifself.father[x]!x:self.father[x]self.find(self.father[x])returnself.father[x]# 为每一个传送层数维护一个并查集防止层与层之间干扰# 多开2位空间防止越界uf[UnionFind(max_val2)for_inrange(k1)]# 4. 分层Dijkstra最短路whileheap:cost,x,y,cntheapq.heappop(heap)# 贪心剪枝当前代价不是最优直接跳过ifcostdist[x][y][cnt]:continue# 首次到达终点即为全局最优解直接返回ifxm-1andyn-1:returncost# ---------------- 操作1普通向下、向右移动 ----------------# 向右移动ify1n:new_costcostgrid[x][y1]ifnew_costdist[x][y1][cnt]:dist[x][y1][cnt]new_cost heapq.heappush(heap,(new_cost,x,y1,cnt))# 向下移动ifx1m:new_costcostgrid[x1][y]ifnew_costdist[x1][y][cnt]:dist[x1][y][cnt]new_cost heapq.heappush(heap,(new_cost,x1,y,cnt))# ---------------- 操作2零成本传送最多k次 ----------------ifcntk:cur_max_valgrid[x][y]# 当前要更新的是 cnt1 传送层cur_ufuf[cnt1]# 从最小值0开始查找第一个未被清空的数值valcur_uf.find(0)# 批量更新所有 cur_max_val 的未更新格子whilevalcur_max_val:# 更新该数值对应的所有格子fornx,nyincells_by_val[val]:ifcostdist[nx][ny][cnt1]:dist[nx][ny][cnt1]cost heapq.heappush(heap,(cost,nx,ny,cnt1))# 标记当前数值已清空合并到下一个数值cur_uf.father[val]cur_uf.find(val1)# 查找下一个未清空数值valcur_uf.find(val)# 题目保证有解不会执行到此处return-1五、逐模块代码深度解析5.1 数值分桶预处理将网格所有坐标按数值分组是并查集批量更新的基础cells_by_val[[]for_inrange(max_val1)]foriinrange(m):forjinrange(n):cells_by_val[grid[i][j]].append((i,j))优势后续可以按数值批量取点无需遍历全网格。5.2 三维距离数组设计dist[[[INF]*(k1)for_inrange(n)]for_inrange(m)]dist[0][0][0]0维度含义dist\[横坐标\]\[纵坐标\]\[已用传送次数\] 最小代价完美适配分层图思想。5.3 并查集核心设计每层传送独立并查集层与层互不干扰uf[UnionFind(max_val2)for_inrange(k1)]路径压缩的并查集保证每次查找近乎 O(1)用于跳过已经批量更新过的数值区间。5.4 普通移动逻辑仅向右、向下移动代价累加目标格子数值不消耗传送次数是传统网格最短路逻辑。5.5 并查集优化传送逻辑核心valcur_uf.find(0)whilevalcur_max_val:# 批量更新所有当前数值的格子fornx,nyincells_by_val[val]:ifcostdist[nx][ny][cnt1]:dist[nx][ny][cnt1]cost heapq.heappush(heap,(cost,nx,ny,cnt1))# 标记清空下次直接跳过cur_uf.father[val]cur_uf.find(val1)valcur_uf.find(val)核心逻辑从最小值开始遍历所有合法、未更新数值批量更新该数值下所有格子的传送层代价更新完成后将该数值合并至下一位永久跳过全程每个数值仅处理一次无冗余计算。六、复杂度严谨分析时间复杂度总状态数O\(m\*n\*k\)≈ 7e4优先队列每次操作log\(mnk\)传送更新均摊每个格子每层仅更新一次O\(mnk\)并查集操作路径压缩均摊 O(1)总复杂度O(m*n*k*log(mnk))Python 轻松AC。空间复杂度三维距离数组 并查集数组 分桶数组O\(m\*n\*k \ max\_val\)完全符合内存限制。七、易错点踩坑总结踩坑1传送可以全局任意点不是只能传送到附近格子暴力遍历必超时踩坑2不同传送层数必须独立并查集共用会导致状态污染、答案错误踩坑3普通移动代价是目标格子数值不是当前格子极易写反踩坑4不做贪心剪枝堆中冗余状态过多导致超时踩坑5终点不能提前break必须等待堆弹出Dijkstra贪心性质首次弹出终点为最优解。八、解题思路总结本题是一道非常经典的图论优化模板题解题三板斧分层图建模将传送次数作为分层维度拆分状态Dijkstra贪心利用非负权值、零传送代价性质证明状态仅需更新一次并查集批量优化解决全局跳转边爆炸问题将暴力 O(N²) 优化为线性均摊复杂度。该优化思想可通用解决带权值阈值全局跳转、有限次数跳跃、批量状态松弛类图论题目非常值得收藏复盘。