[백준]#13911 집 구하기

문제

안양에 사는 상혁이는 4년간의 통학에 지쳐 서울에 집을 구하려고 한다. 상혁이가 원하는 집은 세가지 조건이 있다.

• 맥세권 : 맥세권인 집은 맥도날드와 집 사이의 최단거리가 x이하인 집이다.
• 스세권 : 스세권인 집은 스타벅스와 집 사이의 최단거리가 y이하인 집이다.
• 맥세권과 스세권을 만족하는 집 중 최단거리의 합이 최소인 집

통학 때문에 스트레스를 많이 받은 상혁이는 집을 선택하는 데 어려움을 겪고 있다. 똑똑한 여러분이 상혁이 대신 이 문제를 해결해 주자. 이사 갈 지역의 지도가 그래프로 주어지고 맥도날드와 스타벅스의 위치가 정점 번호로 주어질 때 상혁이가 원하는 집의 최단거리의 합을 출력하는 프로그램을 작성하시오. (맥도날드와 스타벅스가 아닌 정점에는 모두 집이 있다.)

위의 예제 지도에서 사각형은 맥도날드를, 별은 스타벅스가 위치한 정점을 나타낸다. 각 원은 집이 있는 정점을 낸다. x가 6이고 y가 4일 때 가능한 집의 정점은 6이다. 맥도날드까지의 최단거리가 2, 스타벅스까지의 최단거리가 4로 총 합이 6이 되기 때문이다. 정점 7은 맥세권이면서 스세권이지만 맥도날드까지의 최단거리가 6, 스타벅스까지의 최단거리가 2로 총 합이 8로써 정점 6의 값보다 크므로 답이 아니다. 그 외의 정점 2, 3, 4는 맥세권이면서 스세권인 조건을 충족하지 못하므로 답이 될 수 없다.

입력

첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사이에 가중치가 w(1 ≤ w < 10,000)인 도로가 존재한다는 뜻이다. u와 v는 서로 다르며 다른 두 정점 사이에는 여러 개의 간선이 존재할 수도 있음에 유의한다. E+2번째 줄에는 맥도날드의 수 M(1 ≤ M ≤ V-2) 맥세권일 조건 x(1 ≤ x ≤ 100,000,000)가 주어지고 그 다음 줄에 M개의 맥도날드 정점 번호가 주어진다. E+4번째 줄에는 스타벅스의 수 S(1 ≤ S ≤ V-2)와 스세권일 조건 y(1 ≤ y ≤ 100,000,000)가 주어지고 그 다음 줄에 S개의 스타벅스 정점 번호가 주어진다.

• 맥도날드나 스타벅스가 위치한 정점에는 집이 없다.
• 한 정점에 맥도날드와 스타벅스가 같이 위치할 수 있다.
• 집이 있는(= 맥도날드나 스타벅스가 위치하지 않은) 정점이 하나 이상 존재한다.

출력

상혁이가 원하는 집의 맥도날드까지의 최단거리와 스타벅스까지의 최단거리 합을 출력한다. 만일 원하는 집이 존재하지 않으면 -1을 출력한다.

예제 입력 1

8 11
1 2 2
1 4 1
2 4 2
2 3 1
2 7 8
3 7 3
4 5 2
4 6 1
6 7 6
6 8 4
7 8 2
2 6
1 5
1 4
8

예제 출력 1

6

풀이

이 문제는 다익스트라 알고리즘을 이용해서 풀 수 있었다. 처음에는 다익스트라를 일반 Queue를 이용해서 구현했더니 시간이 많이 걸렸었는 데 PriorityQueue(우선순위 큐)를 사용했더니 시간을 반으로 줄일 수 있었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main {
    static int N;
    static ArrayList<Pair>[] graph;
    static PriorityQueue<Pair> queue = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        graph = new ArrayList[N+1];

        for(int i=1; i<=N; i++)
            graph[i] = new ArrayList<>();

        for(int i=0; i<M; i++) {
            input = br.readLine().split(" ");
            int start = Integer.parseInt(input[0]);
            int end = Integer.parseInt(input[1]);
            int cost = Integer.parseInt(input[2]);

            graph[start].add(new Pair(end, cost));
            graph[end].add(new Pair(start, cost));
        }

        int[] mac_dist = new int[N+1];
        for(int i=0; i<=N; i++)
            mac_dist[i] = Integer.MAX_VALUE;

        input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int mac_min = Integer.parseInt(input[1]);
        input = br.readLine().split(" ");

        for(int i=0; i<n; i++) {
            int mac = Integer.parseInt(input[i]);
            mac_dist[mac] = 0;
            queue.add(new Pair(mac, 0));
        }

        dijkstra(mac_dist);

        int[] star_dist = new int[N+1];
        for(int i=0; i<=N; i++)
            star_dist[i] = Integer.MAX_VALUE;

        input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        int star_min = Integer.parseInt(input[1]);
        input = br.readLine().split(" ");

        for(int i=0; i<n; i++) {
            int star = Integer.parseInt(input[i]);
            star_dist[star] = 0;
            queue.add(new Pair(star, 0));
        }

        dijkstra(star_dist);

        int ans = Integer.MAX_VALUE;
        for(int i=1; i<=N; i++) {
            if(mac_dist[i]>0 && mac_dist[i]<=mac_min && star_dist[i]<=star_min && star_dist[i]>0)
                ans = Math.min(ans, mac_dist[i]+star_dist[i]);
        }

        if(ans==Integer.MAX_VALUE)
            System.out.println(-1);

        else
            System.out.println(ans);
    }

    public static void dijkstra(int[] distance) {

        while(!queue.isEmpty()) {
            Pair temp = queue.poll();

            for (int i = 0; i < graph[temp.end].size(); i++) {
                Pair p = graph[temp.end].get(i);

                if (distance[p.end] > p.cost + temp.cost) {
                    queue.add(new Pair(p.end, temp.cost + p.cost));
                    distance[p.end] = temp.cost + p.cost;
                }
            }
        }
    }

    public static class Pair implements Comparable<Pair>{
        int end;
        int cost;

        public Pair(int end, int cost) {
            this.end = end;
            this.cost = cost;
        }

        public int compareTo(Pair p) {

            return this.cost > p.cost ? 1 : -1;
        }
    }
}