[백준] 9370: 미확인 도착지 - JAVA

in Algorithm on 그래프 이론

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

풀이

목적지까지 최단경로에 (g-h)나 (h-g) 도로를 거치는지 확인하는 문제이다.

목적지를 t, 출발지를 s라고 한다면 (s-t)의 거리가 (s-g) + (g-h) + (h-t), (s-h) + (h-g) + (g-t) 두 거리 중 작은 값과 같다면 g-h 도로를 지났다고 확인할 수 있다.

따라서 다익스트라 알고리즘을 사용하여 s부터의 거리 배열, g부터의 거리, h부터의 거리 3개의 배엻을 구한다.

(s-t) 거리가 다른 두 거리 중 작은 값과 같다면 출력한다.

메모리: 63248KB

시간: 676ms

언어: Java 11

코드

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

public class Main {
    static class Node implements Comparable<Node> {
        int v;
        int weight;

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

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.weight, o.weight);
        }
    }

    static int n;
    static ArrayList<ArrayList<Node>> list;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        StringTokenizer st;
        for (int tc = 0; tc < T; tc++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());

            list = new ArrayList<>();
            for (int i = 1; i <= n + 1; i++) {
                list.add(new ArrayList<>());
            }

            for (int i = 0; i < m; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int d = Integer.parseInt(st.nextToken());

                list.get(a).add(new Node(b, d));
                list.get(b).add(new Node(a, d));
            }

            int[] dist_s = dijkstra(s);
            int[] dist_g = dijkstra(g);
            int[] dist_h = dijkstra(h);

            int[] goal = new int[t];
            for (int i = 0; i < t; i++) {
                goal[i] = Integer.parseInt(br.readLine());
            }

            PriorityQueue<Integer> pq = new PriorityQueue<>();
            for (int x : goal) {
                int gh = dist_s[g] + dist_g[h] + dist_h[x];
                int hg = dist_s[h] + dist_h[g] + dist_g[x];
                int sx = dist_s[x];

                if (Math.min(gh, hg) == sx) {
                    pq.add(x);
                }
            }

            while (!pq.isEmpty()) {
                sb.append(pq.poll() + " ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }

    private static int[] dijkstra(int st) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(st, 0));
        dist[st] = 0;

        boolean[] visit = new boolean[n + 1];

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

            if (visit[node.v]) {
                continue;
            }
            visit[node.v] = true;

            for (Node next : list.get(node.v)) {
                if (!visit[next.v] && dist[next.v] > dist[node.v] + next.weight) {
                    dist[next.v] = dist[node.v] + next.weight;
                    pq.add(new Node(next.v, dist[next.v]));
                }
            }

        }

        return dist;
    }

}