다익스트라

다익스트라 기본 코드임.

import java.util.*;

public class Main {
    static final long INF = Long.MAX_VALUE / 4;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int vertexCount = sc.nextInt();
        int edgeCount = sc.nextInt();
        int startVertex = sc.nextInt();

        @SuppressWarnings("unchecked")
        ArrayList<int[]>[] graph = new ArrayList[vertexCount + 1];
        for (int i = 1; i <= vertexCount; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < edgeCount; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            int weight = sc.nextInt();
            graph[from].add(new int[]{to, weight});
        }

        long[] minDistance = new long[vertexCount + 1];
        Arrays.fill(minDistance, INF);
        boolean[] visited = new boolean[vertexCount + 1];

        minDistance[startVertex] = 0L;

        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        pq.offer(new long[]{0L, startVertex});

        while (!pq.isEmpty()) {
            long[] current = pq.poll();
            long currentDist = current[0];
            int currentVertex = (int) current[1];

            // 이미 확정된 정점이면 패스
            if (visited[currentVertex]) continue;
            visited[currentVertex] = true;

            for (int[] edge : graph[currentVertex]) {
                int neighbor = edge[0];
                int weight = edge[1];
                long newDist = currentDist + weight;

                if (newDist < minDistance[neighbor]) {
                    minDistance[neighbor] = newDist;
                    pq.offer(new long[]{newDist, neighbor});
                }
            }
        }

        for (int v = 1; v <= vertexCount; v++) {
            if (minDistance[v] == INF) {
                System.out.println("INF");
            } else {
                System.out.println(minDistance[v]);
            }
        }
    }
}