比较套路的一个题 两种其实差不多的解法 1，DP最短路 回顾最短路的实现中，我们用len[i]len[i]len[i]表示从起点到i这个点的最短距离 那么加入减小边权了呢，我们可以用len[i][j]len[i][j]len[i][j]表示到第i个点，用掉kkk次减少边权机会的最小距离 转移是显然的，在普通最短路转移的基础上，加入从用掉jjj个支援到用j+1j+1j+1个的转移， 最后取min(len[n][i])(i∈[1,k])min(len[n][i])(i∈[1,k])min(len[n][i])(i∈[1,k])即可 2，分层图最短路 本来是有nnn个点的，但是不好处理，我们不妨把每个点拆成k+1k+1k+1个，第jjj个表示到这个点要用jjj次支援 建图的时候同层正常连边，本层到上层连边时边权除222，直接跑最短路，统计答案时枚举第nnn个点各层最小代价即可

思路解析 本题是分层图最短路的又一变体。与前两题（免费边权变 0）不同，这里使用 SpellCard 是将边权减半而非归零。 唯一的区别 Revamping Trails / 飞行路线 冻结 跨层边权 0（免费通行） w/2（时间减半） 其余建图 完全相同 完全相同 数据规模 N ≤ 50，M ≤ 1000，K ≤ 50，非常小。分层图总共才 50×51 = 2550 个节点，甚至 O(n²) Dijkstra 或 SPFA 都能轻松通过。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 逐行注释代码