백준 - 10282 해킹(Java)

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

10282번: 해킹

 

다익스트라 문제입니다.

 

의존성이 주어질 때, 해킹당한 컴퓨터가 몇대의 컴퓨터를 감염 시키는지와 그에 걸리는 시간을 구하는 문제입니다.

각 테스트 케이스마다 시작점이 주어지고, (최소)시간을 구해야 하기 때문에 다익스트라라는 것을 알 수 있습니다.

 

다익스트라의 시간 복잡도는 O(VlogV + ElogV)입니다.

문제에서 최대 V의 개수는 10,000입니다.

또, 최대 E의 개수는 100,000입니다.

따라서 10,000*4 * 100,000*4 = 440,000이기 때문에 허용 시간 내에 있습니다.

 

[구현 코드]

package kr.ac.lecture.baekjoon.Num10001_20000;

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

public class Main {
    private static List<List<Node>> list;
    private static int MAX = 1_000_001_000;

    private static class Node {
        int e, w;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz;

        int testCase = Integer.parseInt(br.readLine());
        while (testCase-- > 0) {
            list = new ArrayList<>();
            stz = new StringTokenizer(br.readLine(), " ");
            int n = Integer.parseInt(stz.nextToken());
            int d = Integer.parseInt(stz.nextToken());
            int c = Integer.parseInt(stz.nextToken());

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

            for (int i = 0; i < d; i++) {
                stz = new StringTokenizer(br.readLine(), " ");
                int a = Integer.parseInt(stz.nextToken());
                int b = Integer.parseInt(stz.nextToken());
                int s = Integer.parseInt(stz.nextToken());

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

            int[] re = dijkstra(n, c);

            bw.write(re[0] + " " + re[1] + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static int[] dijkstra(int n, int c) {
        Queue<Node> qu = new LinkedList<>();
        int[] distance = new int[n + 1];
        Arrays.fill(distance, MAX);

        qu.add(new Node(c, 0));
        distance[c] = 0;
        while (!qu.isEmpty()) {
            Node cn = qu.poll();

            if (cn.w > distance[cn.e]) continue;

            for (int i = 0; i < list.get(cn.e).size(); i++) {
                Node nn = list.get(cn.e).get(i);

                if (distance[nn.e] > distance[cn.e] + nn.w) {
                    distance[nn.e] = distance[cn.e] + nn.w;
                    qu.add(new Node(nn.e, distance[nn.e]));
                }
            }
        }

        int vc = 0;
        int vs = 0;
        for (int i = 0; i < n + 1; i++) {
            if (distance[i] != MAX) {
                vc++;
                vs = Math.max(vs, distance[i]);
            }
        }

        return new int[]{vc, vs};
    }
}