[BOJ/GoldIII] 1238. 파티 - JAVA 자바

1238번: 파티

• 192ms
• 다익스트라

특정 노드에서 모든 노드까지의 최단 경로 계산문제로 다익스트라 구현

 

구해야 하는 것

• go : 1번부터 n번 마을에서 x번 마을로 가는 최단 시간
• back : x번 마을에서 1번~n번 마을로 되돌아가는 최단 시간

여기서 1~n번 마을에서 x번 마을로 가는 최단 시간(go)은

입력으로 주어진 to 와 from 을 반대로 저장한 그래프에서 x번을 출발노드로 하고 1번부터 n번노드까지 가는 최단 경로를 계산하는 것과 일치하다. (처음에는 1~n번 for문 돌며 i번 노드가 출발 노드일 때, x번 까지의 최단 경로를 구했더니 약 900ms 소요)

 

따라서 두 그래프를 선언하여 to-from, from-to 로 저장하고, 다익스트라를 통해 최단 경로를 구한 뒤 가장 오래 걸리는 노드의 소요시간을 출력하였다.

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

public class Main {
    // 다익스트라
    static int n, m, x, result = 0;
    static List<ArrayList<Node>> graphIn = new ArrayList<ArrayList<Node>>();
    static List<ArrayList<Node>> graphOut = new ArrayList<ArrayList<Node>>();
    static int[] go, back;

    // go : 1번 ~ N번 노드가 X번 마을로 가는 데 최소 비용
    // back : X번 마을에서 1~N번 마을로 가는 데 최소 비용

    static class Node implements Comparable<Node> {
        int index;
        int distance;

        public Node(int index, int distance) {
            this.index = index;
            this.distance = distance;
        }

        @Override
        public int compareTo(Node o) {
            return this.distance - o.distance;
        }
    }

    public static void dijkstra(int[] d, List<ArrayList<Node>> graph) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(x, 0));
        d[x] = 0;
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int dist = node.distance;
            int now = node.index;

            if (d[now] < dist)
                continue;

            for (int i = 0; i < graph.get(now).size(); i++) {
                int cost = d[now] + graph.get(now).get(i).dist;

                if (cost < d[graph.get(now).get(i).v]) {
                    d[graph.get(now).get(i).v] = cost;
                    pq.offer(graph.get(now).get(i));
                }

            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        x = Integer.parseInt(st.nextToken());

        back = new int[n + 1];
        go = new int[n + 1];

        for (int i = 0; i <= n; i++)
            graphIn.add(new ArrayList<>());

        for (int i = 0; i <= n; i++)
            graphOut.add(new ArrayList<>());

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int to = Integer.parseInt(st.nextToken());
            int from = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            graphIn.get(to).add(new Node(from, c));
            graphOut.get(from).add(new Node(to, c));
        }

        Arrays.fill(go, Integer.MAX_VALUE);
        Arrays.fill(back, Integer.MAX_VALUE);

        dijkstra(go, graphOut);
        dijkstra(back, graphIn);

        for (int i = 1; i <= n; i++)
            result = Math.max(result, go[i] + back[i]);

        System.out.println(result);
    }

}