题意简析

在一张给定的图上（ $P$ 条双向边），从 $1$ 到 $N$ 找到一条路径，求路径上第 $K + 1$ 长的边的最小边权值

输入格式：第一行三个数$N,P,K$

接下来 $P$ 行每行三个数 $x_i,y_i,z_i$，表示第 $i$ 条边的起点、终点和边权

输入样例 #1

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

输出样例 #1

4

样例解释

题解与代码

由于答案具有单调性，即付钱少的方案一定被包含在付钱多的方案内，那么我们可以二分答案，把问题转化为：是否存在一种合法的升级方法，使花费不超过mid（不超过相当于包含），然后找就行。

在做最短路的时候需要把边权大于mid的边边权变为1，不超过mid的边权为0，然后判断看1到n最短路是否不超过K即可。0到1e6一直二分求出答案，应该不会TLE。

代码