백준 10282 - 해킹

문제

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

리뷰

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

문제의 의존성에 조건에 따르면 주어지는 그래프는 방향 그래프이다.
간선 정보를 저장하고 주어진 감염된 정점 c를 시작점으로 하여
다익스트라를 실행한 후 dist 배열에서 시작점에서 도달할 수 없는
정점임을 의미하는 MAX_VALUE가 아닌 정점들을 카운팅하며 dist 값이
가장 큰 경우를 구하면 총 감염되는 컴퓨터 수, 마지막 컴퓨터가 감염되기까지
걸리는 시간을 도출할 수 있다.

로직의 시간복잡도는 다익스트라의 $O(dlogn)$으로 수렴하며 $n=10,000$,
$d=100,000$인 최악의 경우에도 무난히 제한 조건 2초를 통과한다.

코드

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));
        int T = parseInt(br.readLine());

        int n, d, c;
        int a, b, s;
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            n = parseInt(st.nextToken());
            d = parseInt(st.nextToken());
            c = parseInt(st.nextToken());

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

            while (d-- > 0) {
                st = new StringTokenizer(br.readLine());
                a = parseInt(st.nextToken());
                b = parseInt(st.nextToken());
                s = parseInt(st.nextToken());

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

            dijkstra(c);

            int count = 0;
            int maxDist = MIN_VALUE;

            for (int node = 1; node < dist.length; node++) {
                if (dist[node] == MAX_VALUE) continue;

                if (maxDist < dist[node]) {
                    maxDist = dist[node];
                }

                count++;
            }

            sb.append(count).append(" ").append(maxDist).append("\n");
            graph.clear();
        }

        System.out.print(sb);
        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] > cur.w + next.w) {
                    dist[next.v] = cur.w + 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;
        }
    }
}

결과