백준 18223 - 민준이와 마산 그리고 건우

문제

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

리뷰

다익스트라로 쉽게 풀이할 수 있는 문제였다.

문제에서 결국 요구하는 것은 최단 경로에 건우가 위치한 정점이 포함되어 있니? 인데,
생각을 해보면 다익스트라 알고리즘의 정의는 아래와 같다.

한 시작 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘

따라서 1을 시작점으로 다익스트라 로직을 적용하면 P 와 V (도착점)까지의
최단 경로 비용을 도출할 수 있고, 여기서 P 를 시작점으로 다익스트라 로직을
한번 더 실행하면 $P \rightarrow V$의 최단 경로 비용을 구할 수 있다.

위 과정을 통해 구한 $1 \rightarrow V$와 $1 \rightarrow P \rightarrow V$ 를 비교하여 같으면 아래의 문제 조건에
따라 2번의 다익스트라만으로 답을 도출할 수 있다.

민준이가 건우를 도와주는 경로의 길이가 최단 경로의 길이보다 길어지지 않는다면, 민준이는 반드시 건우를 도와주러 간다.

로직의 시간복잡도는 가장 큰 다익스트라 로직으로 수렴하므로 $O(ElogV)$이고
이는 최악의 경우인 $5000\log10000$의 경우에도 제한 조건인 1초를 무난히
통과한다.

코드

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

import static java.lang.Integer.*;

public class Main {

    static int[] dist;
    static List<List<Node>> graph = new ArrayList<>();

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

        dist = new int[V + 1];
        for (int i = 0; i <= V; i++)
            graph.add(new ArrayList<>());

        while (E-- > 0) {
            st = new StringTokenizer(br.readLine());
            int u = parseInt(st.nextToken());
            int v = parseInt(st.nextToken());
            int w = parseInt(st.nextToken());

            graph.get(u).add(new Node(v, w));
            graph.get(v).add(new Node(u, w));
        }

        dijkstra(1);
        int minCost = dist[V];
        int PCost = dist[P];

        dijkstra(P);
        boolean result = minCost == PCost + dist[V];
        System.out.println(result ? "SAVE HIM" : "GOOD BYE");
        br.close();
    }

    static void dijkstra(int start) { // O(ElogV)
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.weight));
        Arrays.fill(dist, MAX_VALUE);
        dist[start] = 0;
        pq.offer(new Node(start, dist[start]));

        while (!pq.isEmpty()) {
            Node node = pq.poll();

            if (dist[node.num] < node.weight)
                continue;

            for (Node next : graph.get(node.num)) {
                if (dist[next.num] > dist[node.num] + next.weight) {
                    dist[next.num] = dist[node.num] + next.weight;
                    pq.offer(new Node(next.num, dist[next.num]));
                }
            }
        }

    }

    static class Node {
        int num, weight;

        public Node(int num, int weight) {
            this.num = num;
            this.weight = weight;
        }
    }
}

결과