该专栏为热销专栏榜 第15名
本文介绍了华为OD机试中的一道最短路径问题，涉及如何从病毒源计算机出发，计算感染整个局域网所需最短时间。通过使用Dijkstra算法解决图中的单源最短路径问题，同时处理可能存在的不连通情况。文章提供了详细的解题思路、Java算法源码和效果展示。
一、题目描述
一个局域网只内有很多台电脑，分别标注为 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：
1、输入
4
3
2 1 1
2 3 1
3 4 1
2
订阅专栏 解锁全文
扫一扫
1124
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
