華為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);}
}思路：層次遍歷，但是需要按照時間順序排序，兩個點都能到，時間短的在前
