华为od-C卷200分题目4 -电脑病毒感染

华为od-C卷200分题目4 -电脑病毒感染

一个局域网内有很多台电脑，分别标注为0 - N-1的数字。相连接的电脑距离不一样，所以感染时间不一样，感染时间用t表示。其中网络内一个电脑被病毒感染，其感染网络内所有的电脑需要最少需要多长时间。如果最后有电脑不会感染，则返回-1给定一个数组times表示一个电脑把相邻电脑感染所用的时间。如图：path[i]= {i,j, t} 表示电脑i->j 电脑i上的病毒感染j，需要时间t。
输入描述：
4
3
2 1 1
2 3 1
3 4 1
2
输出描述：
2

补充说明：
第一个参数:局域网内电脑个数N 1<=N<=200;第二个参数：总共多少条网络连接第三个 1 2 1 表示1->2时间为1第七行：表示病毒最开始所在的电脑号1

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();ArrayList<List<int[]>> list = new ArrayList<>(n + 1);for (int i = 0; i <= n; i++) {list.add(new ArrayList<>());}int m = sc.nextInt();int a, b, t;while (m-- > 0) {a = sc.nextInt();b = sc.nextInt();t = sc.nextInt();List<int[]> temp = list.get(a);if (temp == null) {temp = new ArrayList<>();}temp.add(new int[]{b, t});list.set(a, temp);}int start = sc.nextInt();PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));queue.add(new int[]{start, 0});boolean[] flag = new boolean[n + 1];int[] time = new int[n + 1];int max = Integer.MIN_VALUE;while (!queue.isEmpty()) {int poll = queue.poll()[0];if (flag[poll]) {continue;}flag[poll] = true;for (int[] ints : list.get(poll)) {time[ints[0]] = time[poll] + ints[1];max = Math.max(time[ints[0]], max);queue.offer(new int[]{ints[0], time[ints[0]]});}}for (int i = 1; i < flag.length; i++) {if (!flag[i]) {System.out.println(-1);return;}}System.out.println(max);}
}

思路：层次遍历，但是需要按照时间顺序排序，两个点都能到，时间短的在前