최소비용 구하기 2

https://www.acmicpc.net/problem/11779

풀이

기존의 최소비용 구하기?와 동일하게 다익스트라 알고리즘을 이용해 최소비용을 구한다. 하지만 문제에서 경로와 거치는 정거장의 수도 출력해야 하기때문에 다익스트라 알고리즘 과정에 하나를 더 추가한다.

route 라는 1차원 배열을 만들고 여기에 출발한 노드의 번호를 집어넣는다.

dist 배열에서 비용이 갱신될 때 route 배열에도 출발한 노드의 번호를 넣게되면 도착지에서 출발지로 역추적이 가능하다.

이를 스택으로 정리하여 출력하면 경로가 나오고, 스택의 사이즈가 거친 정거장의 수이다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Stack;

public class Main {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int n, m;
    static ArrayList<Pair>[] graph;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //String[] input = br.readLine().split(" ");
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        graph = new ArrayList[n + 1];

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

        for (int i = 0; i < m; i++) {
            String[] line = br.readLine().split(" ");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);
            int w = Integer.parseInt(line[2]);
            graph[x].add(new Pair(y, w));
        }
        String[] last = br.readLine().split(" ");
        int start = Integer.parseInt(last[0]);
        int dest = Integer.parseInt(last[1]);

        Entry result = dijkstra(start);
        int[] dist = result.dist;
        int[] route = result.route;

        System.out.println(dist[dest]);
        Stack<Integer> s = new Stack<>();
        int temp = dest;
        s.push(temp);
        while (true) {
            int k = route[temp];
            s.push(k);
            if(k == start) {
                break;
            }
            temp = k;
        }
        System.out.println(s.size());
        while(!s.isEmpty())
            System.out.print(s.pop() + " ");
        bw.close();
        br.close();
    }

    private static Entry dijkstra(int start) {
        int[] dist = new int[n + 1];
        int[] route = new int[n + 1];
        boolean[] visit = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            if (i == start) {
                dist[i] = 0;
                route[i] = 1;
            }
            else
                dist[i] = Integer.MAX_VALUE;
        }
        PriorityQueue<Pair> queue = new PriorityQueue<>();
        queue.offer(new Pair(start, 0));
        while (!queue.isEmpty()) {
            Pair p = queue.poll();
            int y = p.dest;
            if (visit[y])
                continue;
            else
                visit[y] = true;
            for (Pair next : graph[y]) {
                if (dist[next.dest] >= dist[y] + next.weight) {
                    dist[next.dest] = dist[y] + next.weight;
                    route[next.dest] = y;
                    queue.offer(new Pair(next.dest, dist[next.dest]));
                }
            }
        }
        return new Entry(dist, route);
    }

}
class Entry {
    public int[] dist;
    public int[] route;
    public Entry(int[] dist, int[] route) {
        this.dist = dist;
        this.route = route;
    }
}

class Pair implements Comparable<Pair> {
    public int dest;
    public int weight;

    public Pair(int dest, int weight) {
        this.dest = dest;
        this.weight = weight;
    }

    @Override
    public int compareTo(Pair o) {
        return Integer.compare(this.weight, o.weight);
    }
}