https://www.acmicpc.net/problem/1854

문제이해

1차코드

/*
 * 2025-07-25
 * 문제56_백준 1854
 * */
package day8.B1854;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        List<List<Edge>> graph = new LinkedList<>();
        
        
        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());
            Edge edge = new Edge(b,c);
            graph.get(a).add(edge);
        }
        
        // 여기부터 이제..
        
        br.close();
    }
}

원래 처음에는 다이젝스트라 구현하되, k번째까지 반복문 돌려서 하려고 했음

/*
 * 2025-07-25
 * 문제57_백준 1854번
 * */

package day8.B1854;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    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);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int 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 now = current.to;
            int cost = current.weight;

            for (Edge next : graph.get(now)) {
                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();
    }
}

우선순위큐를 역방향으로 해야 하는 이유 : 가장 맨 위에 최댓값이 오는데, 만약 그거보다 작은 값(더 좋은 값)이 들어오면, 값을 바꿔주기 위함.