import java.util.*; import java.io.*; public class Main { static int V, E; static int K; static int[] minCost; static List> graph; static final int INF = Integer.MAX_VALUE; public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st = new StringTokenizer(reader.readLine()); V = Integer.parseInt(st.nextToken()); E = Integer.parseInt(st.nextToken()); K = Integer.parseInt(reader.readLine()); minCost = new int[V + 1]; Arrays.fill(minCost, INF); graph = new ArrayList<>(); for (int i = 0; i <= V; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < E; i++) { st = new StringTokenizer(reader.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken()); graph.get(u).add(new Node(v, w)); } dijkstra(K); for (int i = 1; i < minCost.length; i++) { if (minCost[i] == INF) System.out.println("INF"); else System.out.println(minCost[i]); } } static void dijkstra(int start) { PriorityQueue q = new PriorityQueue<>((n1, n2) -> n1.cost - n2.cost); minCost[start] = 0; q.offer(new Node(start, 0)); while (!q.isEmpty()) { Node now = q.poll(); if (minCost[now.nextNode] < now.cost) continue; for (Node next: graph.get(now.nextNode)) { int newCost = minCost[now.nextNode] + next.cost; if (newCost < minCost[next.nextNode]) { minCost[next.nextNode] = newCost; q.offer(new Node(next.nextNode, newCost)); } } } } static class Node { int nextNode; int cost; public Node(int nextNode, int cost) { this.nextNode = nextNode; this.cost = cost; } } }

코드 #6521