[백준 #11779] 최소비용 구하기 2- JAVA(자바)

문제

n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    public static final int INF = Integer.MAX_VALUE / 2;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        ArrayList<Pair>[] graph = new ArrayList[n+1];

        for(int i = 0; i <= n; i++){
            graph[i] = new ArrayList<>();
        }

        for(int i = 0; i < m; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            graph[s].add(new Pair(e, d));
        }
        String[] split = br.readLine().split(" ");
        int start = Integer.parseInt(split[0]);
        int end = Integer.parseInt(split[1]);

        int[] d = new int[n + 1]; // d[x]: start에서 x까지 최소거리
        int[] pre = new int[n + 1]; // pre[x]: x까지 가는 경로의 바로 뒤 vertex

        Arrays.fill(d, INF);
        Arrays.fill(pre, INF);
        d[start] = 0;
        pre[start] = start;

        PriorityQueue<Pair> pq = new PriorityQueue<>((o1,o2) -> o1.dist - o2.dist);
        pq.add(new Pair(start, 0));
        while (!pq.isEmpty()) {
            Pair cur = pq.poll();
            if(d[cur.node] < cur.dist) continue;

            for(Pair nxt : graph[cur.node]){
                int nxtDist = cur.dist + nxt.dist;
                if(nxtDist < d[nxt.node]){
                    d[nxt.node] = nxtDist;
                    pre[nxt.node] = cur.node;
                    pq.add(new Pair(nxt.node, nxtDist));
                }
            }
        }
        int cnt = 1;
        int node = end;
        StringBuilder sb = new StringBuilder(String.valueOf(end));
        while(node != start){
            node = pre[node];
            sb.insert(0, node+" ");
            cnt++;
        }

        System.out.println(d[end]);
        System.out.println(cnt);
        System.out.print(sb);
    }
}

class Pair{
    int node;
    int dist;

    public Pair(int node, int dist){
        this.node = node;
        this.dist = dist;
    }
}