[白俊]#10282ハッカー

質問する

最悪のハッカーyum 3がネットワーク施設のパソコンに侵入!今、互いに依存しているパソコンが次々と伝染し始めている.あるコンピュータaが別のコンピュータbに依存すると、bがしばらく感染するとaも感染する.このときbがaに依存しなければ,aが感染してもbは安全である.
最も凶暴なハッカーyum 3がハッカーに攻撃されたコンピュータ番号と依存性が与えられた場合、ハッカーに攻撃されたコンピュータを含む数台のコンピュータが感染し、どのくらいの時間がかかるかを求めるプログラムを作成してください.

入力

最初の行は、テスト例の数を示します.テストケースは最大100件です.各テストケースは次のとおりです.

第1行は、コンピュータ個数n、依存個数d、ハッカーによって攻撃されたコンピュータの番号c(1≦n≦10000、1≦d≦100000、1≦c≦n)を与える.

は、次いで、各依存性を表す整数a、b、s(1≦a、b≦n、a≠b、0≦s≦1000)をd行に与える.これは、コンピュータaがコンピュータbに依存し、コンピュータbが感染すると、s秒後にコンピュータaも感染することを意味する.

各テストケースにおいて、同じ依存性(a,b)は2回以上存在しない.

しゅつりょく

各試験例は、1行の総感染コンピュータ数と最後のコンピュータ感染に要する時間をスペースで区切った.

入力例1

2
3 2 2
2 1 5
3 2 5
3 3 1
2 1 2
3 1 8
3 2 4

サンプル出力1

2 5
3 6

に答える

この問題はbfs(幅優先探索)アルゴリズムで解くことができる.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int n;
    static ArrayList<Pair>[] graph;
    static int INF = 10000001;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int i=0; i<T; i++) {
            String[] input = br.readLine().split(" ");
            n = Integer.parseInt(input[0]);
            int m = Integer.parseInt(input[1]);
            int num = Integer.parseInt(input[2]);
            graph = new ArrayList[n+1];
            for(int j=0; j<=n; j++)
                graph[j] = new ArrayList<>();

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

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

            bfs(num);
        }
    }

    public static void bfs(int start) {
        Queue<Pair> queue = new LinkedList<>();
        int[] visited = new int[n+1];
        for(int i=0; i<=n; i++)
            visited[i] = INF;
        queue.add(new Pair(start, 0));
        visited[start] = 0;

        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(visited[p.end]>p.cost+temp.cost) {
                    queue.add(new Pair(p.end, temp.cost+p.cost));
                    visited[p.end] = temp.cost+p.cost;
                }
            }
        }

        int cnt=0;
        int ans=0;

        for(int i=1; i<=n; i++) {
            if(visited[i]!=INF) {
                ans = Math.max(ans, visited[i]);
                cnt++;
            }
        }
        System.out.println(cnt+" "+ans);
    }

    public static class Pair {
        int end;
        int cost;

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