华为OD机试 - 电脑病毒感染 - 最短路径问题（Java 2024 C卷 200分）

华为OD机试 2024C卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

一个局域网只内有很多台电脑，分别标注为 1 ~ N 的数字。相连接的电脑距离不一样，所以感染时间不一样，感染时间用t 表示。

其中网络内一台电脑被病毒感染，求其感染网络内所有的电脑最少需要多长时间。如果最后有电脑不会感染，则返回-1。

给定一个数组 times 表示一台电脑把相邻电脑感染所用的时间: path[i] = {i, j, t} 表示: 电脑i 上的病毒感染 j，需要时间 t 。

二、输入描述

第一行输入一个整数N，表示局域网内电脑个数 N，1 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); // 电脑数量 int M = scanner.nextInt(); // 连接数量 // 使用一个大值初始化邻接矩阵，表示无连接 int[][] graph = new int[N + 1][N + 1]; for (int[] row : graph) { Arrays.fill(row, Integer.MAX_VALUE / 2); // 防止后续运算溢出 } for (int i = 0; i