11779번 최소비용 구하기 2

문제: 최소비용 구하기 2

• 최소 비용 문제이므로 다익스트라로 해결할 수 있습니다.
• 유의해야 할 점은 비용 값이 21억을 넘어갈 수 있으니 비용 계산 시 long을 사용해야 합니다.
• 최단 경로를 기억하기 위해서 int[] parent라는 배열을 생성해서 dist 배열값이 갱신될 때 마다 parent도 갱신해줍니다.
  • parent[nxtNode] = nowNode;
  • parent 배열 각 인덱스의 초기값은 자기 자신입니다.
• 다익스트라로 전부 순회한 뒤 도착 노드부터 parent 배열을 활용해서 역순으로 방문한 노드를 저장해줍니다.
• 현재 도착노드 => 시작노드 순으로 저장을 했으므로 이를 뒤집으면 시작노드 => 도착노드 경로를 구할 수 있습니다.

코드

import java.io.*;
import java.util.*;


public class Main {

    public static int N, M;
    public static List<Integer[]>[] graph;

    static class Pair {
        long cost;
        int node;

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

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

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

        for (int i = 0; i < M; ++i) {
            String[] edgeInfos = br.readLine().split(" ");
            int st = Integer.parseInt(edgeInfos[0]);
            int en = Integer.parseInt(edgeInfos[1]);
            int cost = Integer.parseInt(edgeInfos[2]);

            st--; en--;
            graph[st].add(new Integer[]{en, cost});
        }

        String[] stenInfo = br.readLine().split(" ");

        int st = Integer.parseInt(stenInfo[0]);
        int en = Integer.parseInt(stenInfo[1]);

        st--; en--;

        djikstra(st, en);
    }

    public static void djikstra(int st, int en) {
        int[] parent = new int[N];
        long[] dist = new long[N];

        Arrays.fill(dist, 20_000_000_001L);

        for (int i = 0; i < N; ++i) {
            parent[i] = i;
        }

        PriorityQueue<Pair> pq = new PriorityQueue<>((a,b) -> {
            if (a.cost < b.cost) return -1;
            else if (a.cost == b.cost) return 0;
            else return 1;
        });

        dist[st] = 0;
        pq.add(new Pair(0, st));

        while (!pq.isEmpty()) {
            Pair now = pq.poll();

            long nowCost = now.cost;
            int nowNode = now.node;

            if (dist[nowNode] < nowCost) {
                continue;
            }

            for (Integer[] nxt : graph[nowNode]) {
                int nxtNode = nxt[0];
                int nxtCost = nxt[1];

                if (dist[nxtNode] > nowCost + (long)nxtCost) {
                    dist[nxtNode] = nowCost + (long)nxtCost;
                    parent[nxtNode] = nowNode;
                    pq.add(new Pair(dist[nxtNode], nxtNode));
                }
            }
        }

        int currentNode = en;
        List<Integer> ans = new ArrayList<>();

        while (currentNode != parent[currentNode]) {
            ans.add(currentNode);
            currentNode = parent[currentNode];
        }

        ans.add(currentNode);
        Collections.reverse(ans);

        StringBuilder sb = new StringBuilder();
        for (int node : ans) {
            sb.append(node+1);
            sb.append(" ");
        }

        System.out.println(dist[en]);
        System.out.println(ans.size());
        System.out.println(sb);
    }
}