华为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);
}
}
思路:层次遍历,但是需要按照时间顺序排序,两个点都能到,时间短的在前