BOJ (Java) 11779번: 최소비용 구하기 2

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

 

 

 

---

풀이

다익스트라를 이용해 출발-도착 도시 간의 최소 비용을 구했다.

현재 저장된 비용은 다른 노드들에 의해 갱신되므로 큐에 저장된 비용보다 작을 수 있다. 이런 경우는 실행하지 않아야 이미 방문했지만 큐에 남아있던 도시를 재방문하는 경우를 막을 수 있다.

 

최소 비용의 경로를 구하기 위해, 해당 도시의 직전 도시를 저장해서 경로를 저장했다.
경로는 도착도시부터 시작해서 거슬러 올라갔으며, 출발 도시의 직전 도시는 출발 도시의 값으로 저장해두어

현재 도시 != 직전도시일 때까지 올라가며 저장 후 출력했다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class Main {
    static int MAX_VALUE = 1_000_000_000;
    static int n, m, start, end;
    static int[][] path;
    static int[] before, distance;

    private static void dijkstra() {
        before = new int[n];
        distance = new int[n];
        Arrays.fill(distance, MAX_VALUE);
        boolean[] visited = new boolean[n];

        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Integer.compare(distance[a], distance[b]));
        distance[start] = 0;
        before[start] = start;
        pq.add(start);

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

            if (visited[now]) continue;
            visited[now] = true;

            for (int i = 0; i < n; i++) {
                if (!visited[i] && path[now][i] != MAX_VALUE && distance[now] + path[now][i] < distance[i]) {
                    distance[i] = distance[now] + path[now][i];
                    before[i] = now;
                    pq.add(i);
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // input
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        path = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(path[i], MAX_VALUE);
            path[i][i] = 0;
        }

        for (int i = 0; i < m; i++) {
            String[] tokens = br.readLine().split(" ");
            int first = Integer.parseInt(tokens[0]) - 1;
            int last = Integer.parseInt(tokens[1]) - 1;
            int cost = Integer.parseInt(tokens[2]);
            path[first][last] = Math.min(cost, path[first][last]);
        }

        String[] tokens = br.readLine().split(" ");
        start = Integer.parseInt(tokens[0]) - 1;
        end = Integer.parseInt(tokens[1]) - 1;

        dijkstra();

        // print
        LinkedList<Integer> way = new LinkedList<>();
        way.addFirst(end + 1);
        while (true) {
            int now = way.getFirst() - 1;
            if (now == start) break;

            way.addFirst(before[now] + 1);
        }

        System.out.println(distance[end]);
        System.out.println(way.size());
        for (int w : way)
            System.out.print(w + " ");
    }
}