N1753 - 최단경로

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;


public class Main {
    static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
    static final BufferedWriter BW = new BufferedWriter(new OutputStreamWriter(System.out));
    static final StringBuffer SB = new StringBuffer();
    static StringTokenizer st;
    static Map<Integer, Map<Integer, int[]>> map;
    static int[] dist;
    static int n, m, start;

    public static void main(String[] args) throws IOException {
        input();
        solution(start);
        BW.write(SB.toString());
        BW.close();
        BR.close();
    }

    private static void input() throws IOException {
        int v1, v2, score;

        st = new StringTokenizer(BR.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(BR.readLine());
        map = new HashMap<>();
        dist = new int[n+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        for(int i=1; i<=n; i++)
            map.put(i, new HashMap<>());

        for(int i=0; i<m; i++) {
            st = new StringTokenizer(BR.readLine());
            v1 = Integer.parseInt(st.nextToken());
            v2 = Integer.parseInt(st.nextToken());
            score = Integer.parseInt(st.nextToken());
            if(!map.get(v1).containsKey(v2) || map.get(v1).get(v2)[1] > score)
                map.get(v1).put(v2, new int[] {v2, score});
        }
    }

    private static void solution(int start) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((n1, n2) -> n1[1] - n2[1]);
        int[] curNode;
        int tmp;

        pq.add(new int[] {start, 0});
        dist[start] = 0;

        while(!pq.isEmpty()) {
            curNode = pq.poll();
            if(curNode[1] > dist[curNode[0]])
                continue;

            for(int i : map.get(curNode[0]).keySet()) {
                int[] nextNode =  map.get(curNode[0]).get(i);
                tmp = dist[curNode[0]] + nextNode[1];
                if(tmp < dist[nextNode[0]]) {
                    dist[nextNode[0]] = tmp;
                    pq.add(new int[] {nextNode[0], dist[nextNode[0]]});
                }
            }
        }
        for(int i=1; i<dist.length; i++) {
            if(dist[i] == Integer.MAX_VALUE)
                SB.append("INF").append("\n");
            else
                SB.append(dist[i]).append("\n");
        }
    }
}