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

叁歲伎倆 2024-05-28 10:25 77阅读 0赞

![在这里插入图片描述][986dcebce006483fb6846cb29a3928a7.gif_pic_center]

> 华为OD机试 2024C卷题库疯狂收录中，刷题[**点这里**][Link 1]

### 专栏导读 ###

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

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

### 一、题目描述 ###

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

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

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

### 二、输入描述 ###

第一行输入一个整数N，表示局域网内电脑个数 N，1<= N<= 200 ；

第二行输入一个整数M, 表示有 M 条网络连接；

接下来M行, 每行输入为 i,j,t 。表示电脑 i 感染电脑 j 需要时间t。(1 <= i, j <= N)

最后一行为病毒所在的电脑编号。

### 三、输出描述 ###

输出最少需要多少时间才能感染全部电脑，如果不存在输出 -1

#### 1、输入 ####

4  
3  
2 1 1  
2 3 1  
3 4 1  
2

#### 2、输出 ####

![在这里插入图片描述][8546ab7951614642befa131e95e3edf3.png_pic_center]

### 四、解题思路 ###

这是一个经典的图中的单源最短路径问题，其中节点是电脑，边是电脑间的连接，边的权重是感染时间。可以使用 Dijkstra 算法来解决这个问题，找出从源节点（初始感染的电脑）到所有其他节点的最短路径。此外，我们需要考虑图可能是不连通的情况，如果存在某些节点不可达，则应返回 -1。

具体步骤

1.  初始化图：使用邻接矩阵或邻接表表示图。
2.  Dijkstra 算法：从源节点开始，计算到所有其他节点的最短路径。
3.  处理不可达节点：如果有节点在 Dijkstra 算法完成后仍然是无穷大路径，说明它不可达。
4.  计算最大感染时间：所有电脑都可达时，最长的最短路径即为感染全部电脑所需的最短时间。

### 五、Java算法源码 ###

public class OdTest01 {
        
        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 < M; i++) {
        
                int u = scanner.nextInt();
                int v = scanner.nextInt();
                int t = scanner.nextInt();
                graph[u][v] = Math.min(graph[u][v], t);  // 可能有重复边，取最小值
            }
    
            int start = scanner.nextInt();  // 病毒所在电脑编号
    
            // 使用Dijkstra算法找到从起点到所有点的最短路径
            int[] minTime = dijkstra(graph, N, start);
    
            // 找到最大的最短路径时间，如果有电脑不可达，则返回-1
            int maxTime = 0;
            for (int i = 1; i <= N; i++) {
        
                if (minTime[i] == Integer.MAX_VALUE / 2) {
        
                    System.out.println(-1);
                    return;
                }
                maxTime = Math.max(maxTime, minTime[i]);
            }
    
            System.out.println(maxTime);
        }
    
        private static int[] dijkstra(int[][] graph, int N, int start) {
        
            int[] dist = new int[N + 1];
            boolean[] visited = new boolean[N + 1];
            Arrays.fill(dist, Integer.MAX_VALUE / 2);
            dist[start] = 0;
    
            for (int i = 0; i < N; i++) {
        
                int u = -1;
                int minDist = Integer.MAX_VALUE / 2;
                for (int j = 1; j <= N; j++) {
        
                    if (!visited[j] && dist[j] < minDist) {
        
                        u = j;
                        minDist = dist[j];
                    }
                }
    
                if (u == -1) break;  // 所有可达节点都已访问
                visited[u] = true;
    
                for (int v = 1; v <= N; v++) {
        
                    if (graph[u][v] != Integer.MAX_VALUE / 2 && dist[u] + graph[u][v] < dist[v]) {
        
                        dist[v] = dist[u] + graph[u][v];
                    }
                }
            }
            return dist;
        }
    }

### 六、效果展示 ###

#### 1、输入 ####

4  
3  
2 1 1  
2 3 1  
3 4 1  
3

#### 2、输出 ####

\-1

#### 3、说明 ####

![在这里插入图片描述][853c5f27a185463c8ea82cca20c69901.png_pic_center]

?下一篇：[华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）][OD_ - _ - _Java 2024 C_ 200]

?本文收录于，[华为OD机试（JAVA）真题（A卷+B卷+C卷）][OD_JAVA_A_B_C]

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

![在这里插入图片描述][8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]

[986dcebce006483fb6846cb29a3928a7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/a0e906d7488b485286009f38e3f9bd50.gif
[Link 1]: https://blog.csdn.net/guorui_java/article/details/132683473
[OD_JAVA_A_B_C]: https://blog.csdn.net/guorui_java/category_12293298.html
[8546ab7951614642befa131e95e3edf3.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/ff52891ac1d04ce389103e761d88cc56.png
[853c5f27a185463c8ea82cca20c69901.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/b85fcc1c5fb74bee9a5fec686a30a080.png
[OD_ - _ - _Java 2024 C_ 200]: https://blog.csdn.net/guorui_java/article/details/132197477
[8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/211df074a47144b78b321d7e371127c6.gif