백준(BOJ) 1238: 파티

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

출처: https://steady-coding.tistory.com/106

다익스트라(Dijkstra)는 한정점에서 그 정점을 제외한 다른 모든 정점까지의 최단거리를 구할때 쓰이는 알고리즘이다. 그렇다면 다른 모든 정점에서 그 하나의 정점까지의 각각의 최단거리는 어떻게 구할까? 입력을 반대로 받아서 다익스트라 알고리즘을 적용하면 된다. 

이 문제에서 배운것: 여러개의 정점에서 한정점으로 가는 각각의 최단거리는 출발점과 도착점에 대해 받은 정보를 반대로 적용하여 다익스트라 알고리즘을 적용하면  쉽게 구할 수 있다. 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Testing3 {
    static final int INF = 987654321;

    static class Point implements Comparable<Point> {
        int point;
        int weight;

        Point(int point, int weight) {
            this.point = point;
            this.weight = weight;
        }

        @Override
        public int compareTo(Point p) {
            return weight - p.weight;
        }
    }

    public static int[] dijkstra(List<List<Point>> graph, int start) {
        int size = graph.size();
        PriorityQueue<Point> pq = new PriorityQueue<>();
        int[] dist = new int[size];
        Arrays.fill(dist, INF);
        dist[start] = 0;
        boolean[] visited = new boolean[size];
        pq.add(new Point(start, 0));
        while (!pq.isEmpty()) {
            Point cur = pq.poll();
            if (!visited[cur.point]) {
                visited[cur.point] = true;
                for (var nextV : graph.get(cur.point)) {
                    if (dist[cur.point] + nextV.weight < dist[nextV.point]) {
                        dist[nextV.point] = dist[cur.point] + nextV.weight;
                        pq.add(new Point(nextV.point, dist[nextV.point]));
                    }
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());
        List<List<Point>> graph = new ArrayList<>(n + 1);
        List<List<Point>> reversedGraph = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
            reversedGraph.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 weight = Integer.parseInt(st.nextToken());
            graph.get(start).add(new Point(end, weight));
            reversedGraph.get(end).add(new Point(start, weight));
        }
        int[] dist = dijkstra(reversedGraph, x);
        int[] dist2 = dijkstra(graph, x);
        int answer = 0;
        for (int i = 1; i < n + 1; i++) {
            answer = Math.max(answer, dist[i] + dist2[i]);
        }
        System.out.println(answer);
    }
}

복습: 위와 같이 내부 클래스인 Point자체에 Comparable을 implement하게 할 수도 있지만 Comparable인터페이스를 구현하지 않고 PriorityQueue를 생성할 때

PriorityQueue<Point> pq = new PriorityQueue<>(Comparator.comparingInt(Point::getWeight));

와 같은 식으로 해줄수도 있다.