[백준/자바] #1753

다익스트라 알고리즘을 쓴다는 것까지는 알았는데, java로 구현 방법이 생각나지 않아 다른 풀이를 참고해서 풀었다. 

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.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Main {

    static class Node implements Comparable<Node> {
        public int index;
        public int distance;

        public Node(int index, int distance) {
            this.index = index;
            this.distance = distance;
        }

        @Override
        public int compareTo(Main.Node o) {
            return this.distance - o.distance;
        }

    }

    static int V, E, K;
    static List<Node>[] list;
    static int[] dist;
    static final int INF = 100000000;

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

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(br.readLine());

        list = new ArrayList[V+1];
        for(int i=1; i<V+1; i++) {
            list[i] = new ArrayList<>();
        }
        dist = new int[V+1];
        Arrays.fill(dist, INF);

        for(int i=0; i<E; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            list[start].add(new Node(end, weight));
        }
        
        dijkstra(K);

        StringBuilder sb = new StringBuilder();
        for(int i=1; i<V+1; i++) {
            if(dist[i] == INF) {
                sb.append("INF\n");
            } else {
                sb.append(dist[i] + "\n");
            }
        }
        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }

    private static void dijkstra(int start) {
        boolean[] visited = new boolean[V+1];
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.offer(new Node(start, 0));
        dist[start] = 0;

        while(!queue.isEmpty()) {
            int index = queue.peek().index;
            queue.poll();

            if(visited[index]) {
                continue;
            }
            visited[index] = true;

            for(Node node : list[index]) {
                if(dist[node.index] > dist[index] + node.distance) {
                    dist[node.index] = dist[index] + node.distance;
                    queue.add(new Node(node.index, dist[node.index]));
                }
            }
        }
    }
}