시간 제한 : 2초, 난이도 : 플래티넘, 백준 : 1854번

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Practice58 {

	static final int INF = 100000000; //무한대를 대신하는 큰 값
	public static void main(String[] args) throws IOException{
		int N, M, K;
		int[][] W = new int[1001][1001];
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		PriorityQueue<Integer>[] distQueue = new PriorityQueue[N + 1];
		
		Comparator<Integer> cp = new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o1 < o2 ? 1 : -1;
			}
		};
		for(int i = 0; i < N + 1; i++) {
			distQueue[i] = new PriorityQueue<Integer>(K, cp);
		}
		
		for(int i = 0; i < M ; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			W[a][b] = c;
		}
		
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(1,0));
		distQueue[1].add(0);
		while(!pq.isEmpty()) {
			Node u = pq.poll();
			for(int adjNode = 1; adjNode <= N; adjNode++) {
				if(W[u.node][adjNode] != 0) {
					if(distQueue[adjNode].size() < K) {
						distQueue[adjNode].add(u.cost + W[u.node][adjNode]);
						pq.add(new Node(adjNode, u.cost + W[u.node][adjNode]));
					}
					else if(distQueue[adjNode].peek() > u.cost + W[u.node][adjNode]) {
						distQueue[adjNode].poll();
						distQueue[adjNode].add(u.cost + W[u.node][adjNode]);
						pq.add(new Node(adjNode, u.cost + W[u.node][adjNode]));
					}
				}
			}
		}
		for(int i = 1; i <= N; i++) {
			if(distQueue[i].size() == K) {
				bw.write(distQueue[i].peek() + "\\n");
			}else {
				bw.write(-1 + "\\n");
			}
		}
		bw.flush();
		bw.close();
		br.close();
	}
}

class Node implements Comparable<Node>{
	int node;
	int cost;
	Node(int node, int cost){
		this.node = node;
		this.cost = cost;
	}
	
	@Override
	public int compareTo(Node o) {
		return this.cost < o.cost ? -1 : 1;
	}
}

여진님 코드 참고

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Practice58 {

	public static void main(String[] args) throws IOException{
		int N, M, K;

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		List<List<Edge>> graph = new ArrayList<>();
		for(int i = 0; i <= N; i++) {
			graph.add(new ArrayList<>());
		}
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			graph.get(u).add(new Edge(v, w));
		}
		
		PriorityQueue<Integer>[] dist = new PriorityQueue[N + 1];
		for(int i = 1; i <= N; i++) {
			dist[i] = new PriorityQueue<>(Collections.reverseOrder());
		}
		
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		pq.offer(new Edge(1, 0));
		dist[1].add(0);
		
		while(!pq.isEmpty()) {
			Edge current = pq.poll();
			int to = current.to;
			int cost = current.weight;
			
			for(Edge next : graph.get(to)) {
				int nextNode = next.to;
				int nextCost = cost + next.weight;
				
				if(dist[nextNode].size() < K) {
					dist[nextNode].add(nextCost);
					pq.offer(new Edge(nextNode, nextCost));
				}else if(dist[nextNode].peek() > nextCost) {
					dist[nextNode].poll();
					dist[nextNode].add(nextCost);
					pq.offer(new Edge(nextNode, nextCost));
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i = 1; i <= N; i++) {
			if(dist[i].size() < K) {
				sb.append("-1\\n");
			}else {
				sb.append(dist[i].peek()).append("\\n");
			}
		}
		
		System.out.print(sb);
		br.close();
		
	}
	
	static class Edge implements Comparable<Edge>{
		int to;
		int weight;
		
		public Edge(int to, int weight){
			this.to = to;
			this.weight = weight;			
			
		}
		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.weight, o.weight);
		}
	}

}