백준 12834 - 주간 미팅

문제

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

리뷰

다익스트라로 풀이할 수 있는 간단한 문제였다.

정의된 한 사람의 거리 $d_i$의 합을 구하는 것이 문제의 요구다.
팀원의 위치에서 KIST, 씨알푸드 위치까지의 최단 거리는 팀원의 위치를
시작점으로 다익스트라 로직을 적용하여 구할 수 있고, 유의할 점은 도달 불가능할
경우 거리를 -1로 처리해주어야 한다는 것이다.

로직의 시간복잡도는 $N$개의 팀원 위치를 시작점으로 $O(ElogV)$ 복잡도의
다익스트라 로직을 실행하므로 $O(NElogV)$형태로 수렴하고, 이는 $N=100$,
$E=10,000$,$V=1,000$인 최악의 경우에도 제한 조건 1초를 무난히 통과한다.

코드

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

import static java.lang.Integer.parseInt;
import static java.lang.Integer.MAX_VALUE;

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 N = parseInt(st.nextToken());
        int V = parseInt(st.nextToken());
        int E = parseInt(st.nextToken());

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

        int A, B;
        st = new StringTokenizer(br.readLine());
        A = parseInt(st.nextToken());
        B = parseInt(st.nextToken());

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

        int a, b, l;
        while (E-- > 0) {
            st = new StringTokenizer(br.readLine());
            a = parseInt(st.nextToken());
            b = parseInt(st.nextToken());
            l = parseInt(st.nextToken());

            graph.get(a).add(new Node(b, l));
            graph.get(b).add(new Node(a, l));
        }

        int result = 0;
        for (int start : starts) {
            dijkstra(start);
            result += dist[A] == MAX_VALUE ? -1 : dist[A];
            result += dist[B] == MAX_VALUE ? -1 : dist[B];
        }
        System.out.println(result);
        br.close();
    }

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

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

            if (dist[cur.v] < cur.w)
                continue;

            for (Node next : graph.get(cur.v)) {
                if (dist[next.v] < dist[cur.v] + next.w)
                    continue;

                dist[next.v] = dist[cur.v] + next.w;
                pq.offer(new Node(next.v, dist[next.v]));
            }
        }
    }

    static class Node {
        int v, w;

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

결과