华为OD机试真题---电脑病毒感染

华为OD机试中的“电脑病毒感染”题目是一个典型的图论问题，涉及到网络中的电脑如何通过连接传播病毒，并计算感染所有电脑所需的最短时间。以下是对该题目的详细解析：

一、题目描述

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

二、输入描述

三、输出描述

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

示例1

输入:

输出:

四、代码实现




import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;

public class ComputerVirusInfection {

    /**
     * 计算信号从源节点K传播到所有节点的最短时间
     * 如果无法传播到所有节点，返回-1
     * 使用Dijkstra算法找到从源节点到图中所有其他节点的最短路径
     *
     * @param times  表示图中节点之间的传播时间，每个元素为一个数组，其中包含两个节点和它们之间的传播时间
     * @param N      表示图中节点的总数
     * @param K      表示源节点的编号
     * @return       返回信号传播到所有节点所需的最短时间，如果无法传播到所有节点则返回-1
     */
    public static int networkDelayTime(int[][] times, int N, int K) {
        // 构建图的邻接表
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] time : times) {
            graph.computeIfAbsent(time[0], k -> new ArrayList<>()).add(new int[]{time[1], time[2]});
        }

        // 优先队列，按感染时间从小到大排序
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{K, 0});

        // 记录每个节点的最短感染时间
        Map<Integer, Integer> dist = new HashMap<>();
        dist.put(K, 0);

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int node = current[0];
            int time = current[1];

            if (graph.containsKey(node)) {
                for (int[] neighbor : graph.get(node)) {
                    int nextNode = neighbor[0];
                    int nextTime = neighbor[1] + time;
                    if (!dist.containsKey(nextNode) || nextTime < dist.get(nextNode)) {
                        dist.put(nextNode, nextTime);
                        pq.offer(new int[]{nextNode, nextTime});
                    }
                }
            }
        }

        // 检查是否有未感染的电脑
        if (dist.size() != N) {
            return -1;
        }

        // 找出最长的感染时间
        int maxTime = 0;
        for (int time : dist.values()) {
            maxTime = Math.max(maxTime, time);
        }

        return maxTime;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // 电脑个数
        int M = scanner.nextInt(); // 连接数
        int[][] times = new int[M][3];
        for (int i = 0; i < M; i++) {
            times[i][0] = scanner.nextInt();
            times[i][1] = scanner.nextInt();
            times[i][2] = scanner.nextInt();
        }
        int K = scanner.nextInt(); // 病毒开始的电脑号

        int result = networkDelayTime(times, N, K);
        System.out.println(result);
    }
}

五、解题思路

理解问题：
- 我们有一个由N台电脑组成的局域网，这些电脑之间通过一些连接相互通信。
- 每条连接都有一个特定的传播时间，表示病毒从一个电脑传播到另一个电脑所需的时间。
- 给定一个起始电脑K，我们需要计算病毒传播到所有电脑所需的最短时间。
- 如果存在无法被感染的电脑，则返回-1。
构建图的表示：
- 使用邻接表来表示图，其中每个节点（电脑）都关联一个列表，该列表包含与该节点直接相连的其他节点以及它们之间的传播时间。
- 遍历输入的连接信息times，将每条连接添加到相应的节点列表中。
选择算法：
- 由于我们需要找到从起始节点到所有其他节点的最短路径，我们可以使用Dijkstra算法。
- Dijkstra算法适用于加权图，并且可以找到从单个源节点到所有其他节点的最短路径。
实现Dijkstra算法：
- 使用一个优先队列（最小堆）来存储待处理的节点，队列中的元素按照当前已知的最短路径长度进行排序。
- 初始化队列，将起始节点K及其到自身的距离为0加入队列。
- 使用一个哈希表dist来记录从起始节点到每个节点的最短路径长度。
- 不断从队列中取出当前最短路径的节点，并更新其邻居节点的最短路径长度（如果通过当前节点可以得到更短的路径）。
- 将更新后的邻居节点及其新的最短路径长度加入队列。
检查是否所有节点都被感染：
- 在完成Dijkstra算法后，检查dist哈希表的大小是否等于N（即图中节点的总数）。
- 如果dist的大小小于N，说明存在无法被感染的节点，返回-1。
计算最长感染时间：
- 遍历dist哈希表，找到最长的感染时间（即从起始节点到最远节点的最短路径长度）。
- 返回这个最长感染时间作为结果。
处理输入和输出：
- 从标准输入读取N（电脑个数）、M（连接数）、连接信息times以及起始节点K。
- 调用networkDelayTime函数计算最短感染时间。
- 将结果输出到标准输出。

通过以上步骤，我们可以解决给定的问题，并计算出病毒传播到所有电脑所需的最短时间（如果存在无法被感染的电脑，则返回-1）。

六、运行示例解析

输入

解析步骤

1.读取输入数据：

N = 3：表示图中有3个节点。
M = 3：表示有3条边。
边的数据：
- 2 1 1：表示从节点2到节点1的传播时间为1。
- 2 3 1：表示从节点2到节点3的传播时间为1。
- 3 4 1：表示从节点3到节点4的传播时间为1。
K = 2：表示病毒从节点2开始传播。
2.构建图的邻接表：
graph 的结构如下：

 {
     2: [[1, 1], [3, 1]],
     3: [[4, 1]]
 }

3.初始化优先队列和距离表：

优先队列 pq 初始状态：[[2, 0]]，表示从节点2开始，初始时间为0。
距离表 dist 初始状态：{2: 0}，表示节点2的最短感染时间为0。
4.Dijkstra算法执行过程：
第一次迭代：
- 从优先队列中取出 [2, 0]。
- 更新邻居节点1和3的距离：
  - 节点1：dist[1] = 1，加入优先队列 [[1, 1]]。
  - 节点3：dist[3] = 1，加入优先队列 [[1, 1], [3, 1]]。
第二次迭代：
- 从优先队列中取出 [1, 1]。
- 节点1没有邻居，跳过。
第三次迭代：
- 从优先队列中取出 [3, 1]。
- 更新邻居节点4的距离：
- 节点4：dist[4] = 2，加入优先队列 [[4, 2]]。
第四次迭代：
- 从优先队列中取出 [4, 2]。
- 节点4没有邻居，跳过。

5.检查所有节点是否都被感染：

dist 的最终状态：{2: 0, 1: 1, 3: 1, 4: 2}。
dist.size() == 4，表示所有节点都被感染。

6.找出最长的感染时间：

最长的感染时间 maxTime = 2。

输出

总结

该程序使用Dijkstra算法计算从源节点K传播到所有节点的最短时间。
输入数据表示图的结构和源节点，输出是最长的传播时间。
在这个示例中，从节点2开始，信号传播到所有节点的最短时间为2。

标签：dist,真题,int,感染,OD,电脑,---,队列,节点
From： https://blog.csdn.net/lbp0123456/article/details/143687558