白駿1162道路舗装(JAVA)

質問する
俊英は毎日ソウルから抱川まで通勤する.しかし、十分な睡眠をとっていた俊英はよく朝寝坊をして、遅くまで浦川に着いた.俊英は金持ちで、熟考の末、ソウルから抱川までの時間を短縮するためにK道路を敷くことにした.
問題はN都市があり、その間に道路とこの道路を通るのに要する時間がある場合、少なくとも時間がかかるK以下の道路を梱包することです.道路は舗装するしかなく、舗装して道路を渡るのにかかる時間はゼロです.また、便宜上、ソウルは1番都市、浦川はN番都市であり、1番からN番までの頻繁な到着データしか提供していない.
入力
1行目は、都市数N(1≦N≦10000)、道路数M(1≦M≦50000)、舗装する道路数K(1≦K≦20)をスペースで区切っている.M線については,道路が接続された2つの都市と道路を通過するのに要する時間を与える.道路は双方向であり、所要時間は1000000以下の自然数である.
しゅつりょく
1行目はk本以下の道路を舗装し,得られる最小時間を出力する.
に答える
包装k本以下の道路は、j号都市までの最小時間をdp[j][k]に設定し、複数の曲線を回し、最小値を保存する.これまで舗装されていた道路カウントからもう1つ削除した場合(この場合、次のedgeのコストは増加しない)をチェックし、dpを充填します.

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

public class Main {
    static int N, M, K;
    static long[][] dp;
    static class Edge {
        int end,count;
        long cost;

        public Edge(int end, long cost, int count) {
            this.end = end;
            this.cost = cost;
            this.count = count;
        }
    }
    static ArrayList<Edge>[] edges;
    static final long MAX = Long.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        edges = new ArrayList[N + 1];
        dp = new long[N + 1][K + 1];
        for (int i = 1; i <= N; i++) {
            edges[i] = new ArrayList<>();
            Arrays.fill(dp[i], MAX);
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            edges[s].add(new Edge(e, c, 0));
            edges[e].add(new Edge(s, c, 0));
        }

        dijkstra();
        long min = MAX;
        for (long a : dp[N]) {
            min = Math.min(a, min);
        }
        bw.write(min + "\n");
        bw.flush();
        bw.close();
    }
    static void dijkstra() {
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingLong(o -> o.cost));
        pq.add(new Edge(1, 0, 0));
        dp[1][0] = 0;

        while(!pq.isEmpty()) {
            Edge cur = pq.remove();
            if (cur.cost > dp[cur.end][cur.count]) continue;
            for (Edge next : edges[cur.end]) {
                long nextCost = next.cost + cur.cost;
                if(nextCost < dp[next.end][cur.count]) {
                    dp[next.end][cur.count] = nextCost;
                    pq.add(new Edge(next.end, nextCost, cur.count));
                }
                if (cur.count < K && cur.cost < dp[next.end][cur.count + 1]) {
                    dp[next.end][cur.count + 1] = cur.cost;
                    pq.add(new Edge(next.end, cur.cost, cur.count + 1));
                }
            }
        }
    }
}