[백준] 12843. 주간 미팅(Java)

문제

12834번: 주간 미팅

 

풀이

집에서 목적지(KIST, 씨알푸드) 2곳에 모두 도달하는지 여부와, 도달 한다면 모든 사람의 최단 거리의 합을 출력하는 문제입니다.

한 사람의 최단 거리는 (집-KIST의 최단 거리) + (집-씨알푸드의 최단 거리)

도달하지 못하면 최단 거리는 -1

 

따라서, 집 기준으로 다익스트라를 이용해서 도달 여부 및 최단 거리를 구해주면 됩니다.

 

코드

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

class Main {
    static final int INF = 1 << 30;
    static int A, B;
    static int[] dist;
    static List<Node>[] list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
//        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken()); // 팀원 수
        int V = Integer.parseInt(st.nextToken()); // 장소 수
        int E = Integer.parseInt(st.nextToken()); // 도로 수

        st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken()); // KIST 위치
        B = Integer.parseInt(st.nextToken()); // 씨알푸드 위치

        int[] friend = new int[N];
        dist = new int[V+1];
        list = new ArrayList[V+1];

        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < N ; i ++)
            friend[i] = Integer.parseInt(st.nextToken());

        for(int i = 1 ; i <= V ; i ++){
            list[i] = new ArrayList<>();
        }

        for(int i = 0 ; i < E ; 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[a].add(new Node(b, d));
            list[b].add(new Node(a, d));
        }

        int sum = 0;
        for(int i = 0 ; i < N ; i ++)
            sum += dijkstra(friend[i]);

        System.out.println(sum);
    }

    private static int dijkstra(int s) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        Arrays.fill(dist, INF);
        dist[s] = 0;
        pq.offer(new Node(s, 0));

        while(!pq.isEmpty()){
            Node curNode = pq.poll();
            int cur = curNode.n;

            if(curNode.d > dist[cur]) continue;

            for(Node next: list[cur]){
                if(dist[next.n] > dist[cur] + next.d){
                    dist[next.n] = dist[cur] + next.d;
                    pq.offer(new Node(next.n, dist[next.n]));
                }
            }
        }

        return ((dist[A] == INF) ? -1 : dist[A]) + ((dist[B] == INF) ? -1 : dist[B]);
    }

    static class Node implements Comparable<Node>{
        int n, d;

        public Node(int n, int d){
            this.n = n;
            this.d = d;
        }

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