双端队列+二分
根据题意，一条路径的长度就被定义为第$k+1$长的边权，如果边数小于等于$k$，则路径长度为$0$.
所以要求的就是从节点$1$到节点$n$的路径中第$k+1$大的值的最小值，于是想到用二分。
可以用二分的情况是所求的答案在某个分界点，具有某个性质，在这个分界点的一边满足这个性质，另一边不满足
本题中的区间长度被定义为$[0 , 1e6+1]$
为了证明我们所求的答案的确可以通过二分来找到，我们需要说明所求的答案具有某种性质，且在它的右边满足，左边不满足：
1.对于答案x，需要满足的性质就是从$1$走到$n$需要经过大于$x$的边数小于等于$k$，作为分界点，此时大于$x$的边数应该等于$k$。
2.对于答案右边的区间，$x$变大了，大于$x$的边数就会减小，即大于$x$的边数小于$k$，同样满足性质；
2.对于答案左边的区间，$x$变小了，大于$x$的边数就会增加，即大于$x$的边数大于$k$，不满足性质。
因此可以用二分
接下来的问题就是如何判断是否满足性质？
在这里我们将大于$x$的边权设置为$1$，小于等于$x$的边权设置为$0$，那么只需要判断一条路径的长度是否小于等于$k$即可，如果长度小于等于$k$说明满足，否则不满足。
于是问题转换成在一幅$01$图中，找最短路径，这就可以用双端队列来做（参考 AcWing 175. 电路维修 ）
于是通过不断二分就能找到最小的第k+1大的数！
分析区间边界：
一、从实际情况出发可以知道，如果$k>$一条路径的边数则结果为0；
二、如果右边界为$1e6$，则会有两种情况结果为$1e6$：
①当$1$走不到$N$时，由于二分的特性，最终会返回右边界，即$1e6$
②当$1$走到$N$时，但最终的花费是$1e6$，结果返回$1e6$（例如$1$到$N$的路径经过两条长度都是$1e6$的边，$k=1$，此时结果就是$1e6$）
因此为了区分这两种情况需要将右边界定义成$1e6+1$
C++ 代码
#include <iostream>
#include <cstring>
#include <deque>
#include <algorithm>
using namespace std;
const int N = 1010 , M = 20010;
int e[M] , ne[M] , w[M] , h[N] , idx;
int dist[N];
int n , m , k;
bool st[N];
void add(int a , int b , int c)
{
e[idx] = b , ne[idx] = h[a] , w[idx] = c , h[a] = idx++;
}
bool check(int bound)
{
memset(dist , 0x3f , sizeof dist);
memset(st , 0 , sizeof st);
dist[1] = 0;
deque<int> q;
q.push_back(1);
while(q.size())
{
int t = q.front();
q.pop_front();
if(st[t]) continue;
st[t] = true;
for(int i = h[t] ; ~i ; i = ne[i])
{
int j = e[i] , x = w[i] > bound;
if(dist[j] > dist[t] + x)
{
dist[j] = dist[t] + x;
if(x) q.push_back(j);
else q.push_front(j);
}
}
}
return dist[n] <= k;
}
int main()
{
cin >> n >> m >> k;
memset(h , -1 , sizeof h);
while(m--)
{
int a , b , c;
cin >> a >> b >> c;
add(a , b , c) , add(b , a , c);
}
int l = 0 , r = 1e6 + 1;
while(l < r)
{
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
if(r == 1e6 + 1) r = -1;
cout << r << endl;
return 0;
}
贴一个另一种版本根据大佬思路写的C++代码：
有没有一种可能，我是说可能，这个二分出来的值不存在边权里面
没有
今天回顾这道题，我也在想这个问题，能说一下为什么吗？谢谢大佬。
如果二分出来的值不在边权中，此时该值必然使得check()返回true（如果返回false连条件都不满足，肯定不会是答案），那么就会缩小右边界继续二分，直到找到满足条件的最小值。注意这道题二分的本质仍是找到满足条件的最小值。
懂了，谢谢
对呀，如果不存在这个二分值的话，返回的肯定是上一次二分的结果
和名字配合得很好😅
很好奇为什么二分出来的r一定某条边的边权，感觉是对的，不知道怎么表达出来
可以看看证明过程
二分答案懂吧，这题其实你可以想象成二分答案，如果有个边权为x，那么大于x的数有少于k条，那么我就可以缩小右边界，如果大于k条，增大左边界，同理不断缩小区间就一定能找到
反正答案都在区间内
大佬，这个x如果变大了，那么不是大于x的边应该变少么?那这个x作为答案不是不正确了吗？因为x可以取更小啊，求解惑
对于x可以取得的条件是，从1走到n，经过花费大于x的边数要
小于等于k。比如当前x为8，K为3，路径上超过8的边数只有2条，但是如果农场主选择支付8还是成立的，只是不是最优的，最优的解需要进一步二分才能得出。
当前这个x虽然满足条件，但不一定就是最后的结果，需要不断二分才能找到最后的值。
哦哦，有点明白了，谢谢大佬
我还是不理解为什么边权等于0就放对头，等于1就放队尾？
难道是和小根堆优化版的迪杰特斯拉里的小根堆里头放距离是一样的吗？因为会小的先出堆，大的后出，这题的0放对头1放队尾是一样的意思吗？
可以点题解里的链接 参考电路维修那道题
参考bfs两段性的证明
在哪？
百度或者y总讲bfs为什么能做最短路那一课
💕
记录美好生活
写的太好了！
谢谢hh~
神奇的二分
qs
用vector最后一个点t了😅
vector说：我常数有点大，你得忍一忍vector是一种占用空间比较小，但是调用的时候会需要时间很多吗
写的题解太好了， 我看哭了o(╥﹏╥)o
啊这😅
大佬，为什么以mid为分界点，右边满足某种性质，左边不满足某种性质。但是check成功后，答案却在左边，而不是在右边呢？右边满足某种性质，答案不应该往右边寻找嘛？
因为求的是最小值，所以当check后，我们可以将答案范围缩小到
(l,mid)如果求的是第k+1的最大值呢
这题做太久忘记题意了，忽略之前的回复，这题求的就是第k+1大的值呀
最大值就需要用二分的另一个模板了，mid=l+r+1>>1
您 tql，积极向大佬看齐，每天多a一道！
啊 我不是大佬Orz
为什么要用双端队列哇
因为这里边权只有是0或1，如果u->v的边权为0，将v点推入队头，如果边权为1，将v点推入队尾。
这样做就可以保证队列的两段性和单调性，可以说明队列是非降序的。
用小根堆也是可以的，但是小根堆的插入取出是要O(logn)的，用双端队列是O(1)的。
你可以去看一下 https://www.acwing.com/solution/content/13633/ 这一题，是这道题的一个前导。