这里提供两种解题思路

1.dp+spfa

题意理解

就是让你从起点1,到终点N,找一条代价最少的路径,每一条路径的代价是这条路径上的最大权值,且你可以指定一条路径上K条边权值为零.

思路解析

首先我们一眼就可以确定这道题目是的最短路算法.毕竟题目上白纸黑字上写着要,求出最短路.



首先我们一步步分析一下,这道题目的几个关键点.



这道题目的路径代价是什么?

我们发现,这里的路径不同于一般的最短路,每一条路径的最大边是这条路径的花费



题目中有些路径可以清零,这怎么办?

所有关于边的条件或者性质,其实都可以认为是一种特殊边.



这道题目中,有些边可以代价为0,那么我们不妨设置一种特殊边.



比如说(a,b)是相连的边,他们代价是c,那么如果说我们让它免费,不就是又多了一条边,(a,b),只不过他们的代价是0?



所谓的路径可以免费,就是多了一条为0的重边.



所以这道题目的性质,转换一下就是,我们可以设置K条为权值0的边.



所以我们可以设置一个数组d[x,p]表示从1号节点到x号节点,途中经过p条权值为0的边,



新加入的边是非0边.

那么我们面对每一条新加入的边(x,y,z)我们的d[y,p]=max(d[x,p],z),其中zz为(x,y)权值.



新加入的边是0边.

如果新加入的边是权值为0的边,显然是d[y,p+1]=d[x,p]d[y,p+1]=d[x,p].



完整题解：https://www.acwing.com/solution/content/2425/





2.二分+双端队列

根据题意，一条路径的长度就被定义为第k+1长的边权，如果边数小于等于k，则路径长度为0.

所以要求的就是从节点1到节点n的路径中第k+1大的值的最小值，于是想到用二分。



可以用二分的情况是所求的答案在某个分界点，具有某个性质，在这个分界点的一边满足这个性质，另一边不满足



本题中的区间长度被定义为[0,1e6+1]



为了证明我们所求的答案的确可以通过二分来找到，我们需要说明所求的答案具有某种性质，且在它的右边满足，左边不满足：

1.对于答案x，需要满足的性质就是从11走到nn需要经过大于x的边数小于等于k，作为分界点，此时大于x的边数应该等于k。

2.对于答案右边的区间，x变大了，大于x的边数就会减小，即大于x的边数小于k，同样满足性质；

2.对于答案左边的区间，x变小了，大于x的边数就会增加，即大于x的边数大于k，不满足性质。



因此可以用二分



接下来的问题就是如何判断是否满足性质？

在这里我们将大于x的边权设置为1，小于等于x的边权设置为0，那么只需要判断一条路径的长度是否小于等于k即可，如果长度小于等于k说明满足，否则不满足。

于是问题转换成在一幅01图中，找最短路径，这就可以用双端队列来做





完整题解：https://www.acwing.com/solution/content/13645/

算法竞赛进阶指南