方法1 DIJ算法

import java.io.*;
import java.util.*;

public class Main {

    private static int n, p, k;
    private static int N = 1010;
    private static int M = 10010 * 2;
    private static int[] h = new int[N];
    private static int[] e = new int[M];
    private static int[] ne = new int[M];
    private static int[] w = new int[M];
    private static int idx = 0;
    private static int[] dist = new int[N];
    private static boolean[] st = new boolean[N];
    private static class Node {
        int d;
        int t;

        public Node(int d, int t) {
            this.d = d;
            this.t = t;
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        p = Integer.parseInt(s[1]);
        k = Integer.parseInt(s[2]);
        Arrays.fill(h, -1);
        while (p-- > 0) {
            String[] ss = br.readLine().split(" ");
            int a = Integer.parseInt(ss[0]);
            int b = Integer.parseInt(ss[1]);
            int c = Integer.parseInt(ss[2]);
            add(a, b, c);
            add(b, a, c);
        }
        int l = 0;
        int r = 1000001;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (DIJ(mid))
                r = mid;
            else
                l = mid + 1;
        }
        if (l == 1000001)
            System.out.print(-1);
        else
            System.out.print(l);

    }

    private static boolean DIJ(int bound) {
        Queue<Node> queue = new PriorityQueue<>((v1, v2) -> v1.d - v2.d);
        queue.add(new Node(0, 1));
        Arrays.fill(dist, 0x3f3f3f3f);
         Arrays.fill(st, false);
        dist[1] = 0;
        while (!queue.isEmpty()) {
            Node t = queue.poll();
            if (st[t.t])
                continue;
            st[t.t] = true;
            for (int i = h[t.t]; i != -1; i = ne[i]) {
                int j = e[i];
                int v = w[i] > bound ? 1 : 0;
                if (dist[j] > t.d + v) {
                    dist[j] = t.d + v;
                    queue.add(new Node(dist[j], j));
                }
            }
        }
        return dist[n] <= k;
    }
    private static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}

方法2 双端BFS

import java.io.*;
import java.util.*;

public class Main {

    private static int n, p, k;
    private static int N = 1010;
    private static int M = 10010 * 2;
    private static int[] h = new int[N];
    private static int[] e = new int[M];
    private static int[] ne = new int[M];
    private static int[] w = new int[M];
    private static int idx = 0;
    private static int[] dist = new int[N];
    private static boolean[] st = new boolean[N];
    private static Deque<Integer> deque = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        p = Integer.parseInt(s[1]);
        k = Integer.parseInt(s[2]);
        Arrays.fill(h, -1);
        while (p-- > 0) {
            String[] ss = br.readLine().split(" ");
            int a = Integer.parseInt(ss[0]);
            int b = Integer.parseInt(ss[1]);
            int c = Integer.parseInt(ss[2]);
            add(a, b, c);
            add(b, a, c);
        }
        int l = 0;
        int r = 1000001;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid))
                r = mid;
            else
                l = mid + 1;
        }
        if (l == 1000001)
            System.out.print(-1);
        else
            System.out.print(l);

    }

    private static boolean check(int bound) {
        Arrays.fill(dist, 0x3f3f3f3f);
        Arrays.fill(st, false);
        dist[1] = 0;
        deque.addLast(1);
        while (!deque.isEmpty()) {
            int t = deque.poll();
            if (st[t])
                continue;
            st[t] = true;
            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                int v = w[i] > bound ? 1 : 0;
                if (dist[j] > dist[t] + v) {
                    dist[j] = dist[t] + v;
                    if (v == 0)
                        deque.addFirst(j);
                    else
                        deque.addLast(j);
                }
            }
        }
        return dist[n] <= k;
    }

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