思路解析 问题本质 从节点 1 到节点 N 的最短路，但可以将最多 K 条边的权值变为 0。 核心思路：分层图 构建 K+1 层图（第 0 层到第 K 层），每一层代表"已经使用了多少次免费改造"： * 层内边：对于原图每条边 (u, v, w)，在每一层都保留原边 u → v（权 w） * 跨层边：对于原图每条边 (u, v, w)，添加从第 j 层到第 j+1 层的边 u → v（权 0），表示"改造这条边" 从第 0 层的节点 1 出发跑 Dijkstra，答案是 minj=0Kdist[第 j 层的节点 N]min_{j=0}^{K}\text{dist}[\text{第 j 层的节点 N}]minj=0K dist[第 j 层的节点 N]。 图解 复杂度 * 节点数：N×(K+1)N \times (K+1)N×(K+1) * 边数：M×(K+1)×2M \times (K+1) \times 2M×(K+1)×2（层内）+ M×K×2M \times K \times 2M×K×2（跨层） * 时间：O(K⋅(N+M)log(NK))O(K \cdot (N + M) log(NK))O(K⋅(N+M)log(NK)) * 空间：O(NK+MK)O(NK + MK)O(NK+MK) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 逐行注释代码