$$\color{Red}{通信线路(最易懂的证明)——【从0推演到->双端队列二分】}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

解析

这道题运用了双端队列->dijkstra的两端性性质 -> 我的电路维修题解

根据题意，一条路径的长度就被定义为第k＋1长的边权，如果边数小于等于k，则路径长度为0.所以要求的就是从节点1到节点n的路径中第k＋1大的值的最小值，于是想到用二分。

首先这道题，初见直觉的思路，暴力dfs，而形参保存当前全部路径长度，最长路径，以及经过几条路径等需要的参数，然后进行最优剪枝，即一旦已经比当前最优差，即扣除k条最长边，剩下的边中最大值更大直接ruturn。

这个思路想了一半因为复杂度太大，且找到合适的简单表达出第k＋1长的边权长度的方式过于麻烦而放弃。

遂看y总的二分+双端队列思路。

y总：找寻一个满足第 xx 的量的值 往往可以使用二分去优化

首先这道题定义， 我们二分的区间是 [0 - > 1e6 + 1]

为什么是这个值？等整个模型说完再解释。

我们该怎么找出单调性？或者说两段性？

我们可以这么理解，我们能让 前 k 个长度的路径费用降为0 ， 那么理论上我们可以二分去找一个长度 x，判断这个长度相等以下的值的边权都是0，大于x的值都设置为1，利用双端队列【具体细节在上面的题解有，不懂得可以去看看】，这样最后算出来的 d[n] 最短路的值，不就是满足边权大于等于x的边的数量了。

那和二分以及找寻答案有什么关系？

结合我上面说的暴力的思路，我们其实暴力最大的局限就是，搜索的时候是盲目搜索，不知道该搜怎么样的路径，虽然有个最优剪枝，但是在第一次到终点前都没有优化的机会，万一这道题都不联通，岂不是直接TLE？

而目前引出的二分，首先解决了盲目搜索的问题，其次，我们还找到一个很容易表示出一条路径中，长度大于x的边的数量，这已经很接近我们想要完成的表达出第 k ＋ 1 长的边权长度的思想了。

怎么把 x 和 表达出第 k ＋ 1 长的边权长度牵扯上关系？

我们要思考一个性质，二分到底把区间划分成怎样的两段区间？ x 越大，满足的边数量一定越小，满足的边数量，不正是所谓的边权大于等于 x 的边数量，如果我们把这个数量限制等于 k ，岂不是我们不需要知道到底这最大的 k 条边具体的值【根据上面的限制，这 k 条边严格大于 x 】，然后我们设定我们选取答案的分解线，即答案为最小的 x 且满足大于 x 的边数为 k，它就是我们要找的第 k + 1 长的边，且满足最优【x最小】

这么做真的对吗？【因为二分的条件需要做到两段性 即左边的值和右边的值能由二分条件分隔 保证答案的唯一性】

右移是否满足均劣于答案的值？

我们这么想，答案右移，即增大 x，此时此时大于 x 的边数一定会减少或不变，即我们此时的 x 增大了长度。如果边数减少，那就比 k 小，那么 x 就不是 第 k + 1 长的边了，直接非答案，pass。即便是 大于 x 的边数量仍是 k ，但显然我们右移增大的 x，明明可以取答案更小的 x，即并非最优，仍能进行二分去接近答案。

故答案右边的点都不能取，证毕。

左移是否满足均劣于答案的值？

我们这么想，答案左移，即减小 x，此时此时大于 x 的边数一定会增多，不可能不变【我们假设的答案点就是最小的 x且满足 第 k + 1 长的边的情况】，即我们此时的 x 减小了长度。边数增多的情况，那就比 k 大，那么 x 就不是 第 k + 1 长的边了，直接非答案，pass。

故答案左边的点都不能取，证毕。

严格证明结束，此时回到问题最开始的为什么二分区间是 [0 - > 1e6 + 1]？

先思考一个问题，有没有可能 x 即，我们最终花费得值为0， 当然有可能，如果 k 的值为3，1 -> n 只经过2条边，直接就是免费，即 二分区间有 0 是为了搜到左边界的情况。

那为什么要多开 1 个位置？

因为有一种可能， 第 k + 1 长的边，就等于我们题目限制输入的最大值，此时 x 可以等于 1e6。但是也有种可能，这道题根本 1 -> n不联通，那么二分过程中 x值无论取多少，都会满足 d[n] >= k 大【无穷】，算法会使得继续扩大 x，使得 d[n] 缩小以逼近 k，但是因为不连通，只能一直扩大，此时如果不多开一个位置，存不连通的情况，就无法区分出答案刚好为最大边长的情况，和不连通的情况。故多开一个专门预防右边界。

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;


/**
 * @author Fanxy
 */
public class Main {

    private static final int INF = 0x3f3f3f3f;
    static int n, m, k, idx, N = 10010, M = 2 * N;
    static int[] h = new int[N];
    static int[] e = new int[2 * M];
    static int[] ne = new int[2 * M];
    static int[] w = new int[2 * M];

    static void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = h[a];
        w[idx] = c;
        h[a] = idx++;
    }

    static boolean check(int x) {
        LinkedList<Integer> queue = new LinkedList<>();
        int[] d = new int[N];
        boolean[] st = new boolean[N];
        Arrays.fill(d, INF);
        queue.add(1);
        d[1] = 0;
        while (!queue.isEmpty()) {
            int top = queue.remove();
            if (st[top]) continue;
            st[top] = true;

            for (int i = h[top]; i != -1; i = ne[i]) {
                int j = e[i];
                int dist = 0;
                if (w[i] > x) dist = 1;
                if (d[j] > dist + d[top]){
                    d[j] = dist + d[top];
                    if (dist == 1) queue.add(j);
                    else queue.addFirst(j);
                }
            }
        }

        return d[n] <= k;
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        Arrays.fill(h, -1);
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        k = Integer.parseInt(s1[2]);
        for (int i = 0; i < m; i++) {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            int c = Integer.parseInt(s2[2]);
            add(a, b, c);
            add(b, a, c);
        }

        int l = 0, r = (int) 1e6 + 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        if (l == (int) 1e6 + 1) l = -1;
        System.out.println(l);
    }
}