[백준 / 골드3] 1238 파티 (Java)

문제 보기

사용한 것

• 한 정점에서 출발 후 다른 정점에 도착하는 최단 비용을 구하기 위한 다익스트라

풀이 방법

• 특정 정점에서 모든 정점까지의 최소 시간은 다익스트라로 구한다.
• 모든 정점에서 출발하여 x에 도착하는 시간들을 goTimes에 저장한다.
• x에서 출발하여 모든 정점에 도착하는 시간들을 comeTime에 저장한다.
• goTimes[i] + comeTimes[i]의 최대값을 구한다.

코드

public class Main {

    private static int n;
    private static int m;
    private static int x;
    private static List<List<Node>> graph;

    public static void main(String[] args) throws IOException {
        init();
        System.out.println(findMaxTime());
    }

    private static void init() 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());
        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
            graph.get(start).add(new Node(end, time));
        }
        br.close();
    }

    private static int findMaxTime() {
        int maxTime;
        int[] goTimes = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            goTimes[i] = getTimes(i)[x];
        }
        int[] comeTimes = getTimes(x);
        maxTime = getMax(goTimes, comeTimes);
        return maxTime;
    }

    private static int[] getTimes(int startVertex) {
        int[] times = new int[n + 1];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        Arrays.fill(times, Integer.MAX_VALUE);
        times[startVertex] = 0;
        pq.offer(new Node(startVertex, 0));
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int vertex = node.getVertex();
            int time = node.getTime();
            if (time < times[vertex]) {
                continue;
            }
            for (Node nextNode : graph.get(vertex)) {
                int nextVertex = nextNode.getVertex();
                int nextTime = time + nextNode.getTime();
                if (nextTime < times[nextVertex]) {
                    times[nextVertex] = nextTime;
                    pq.offer(new Node(nextVertex, nextTime));
                }
            }
        }
        return times;
    }

    private static int getMax(int[] arr1, int[] arr2) {
        int max = 0;
        for (int i = 1; i <= n; i++) {
            max = Math.max(arr1[i] + arr2[i], max);
        }
        return max;
    }
}

class Node implements Comparable<Node> {

    private final int vertex;
    private final int time;

    public Node(int vertex, int time) {
        this.vertex = vertex;
        this.time = time;
    }

    public int getVertex() {
        return vertex;
    }

    public int getTime() {
        return time;
    }

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