华为OD统一考试 - 电脑病毒感染
题目描述
一个局域网内有很多台电脑,分别标注为 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
用例
输入 |
4 3 2 1 1 2 3 1 3 4 1 2 |
输出 |
2 |
说明 |
第一个参数:局域网内电脑个数N,1 ≤ N ≤ 200; 第二个参数:总共多少条网络连接 第三个 2 1 1 表示2->1时间为1 第六行:表示病毒最开始所在电脑号2 |
题目解析
用例图示如下
病毒源头是2,其中:
2->1需要时间1
2->3需要时间1,3->4需要时间1
因此最少需要时间2才能感染所有电脑。
另外,本题题目描述和用例不符。因为题目说:
一个局域网内有很多台电脑,分别标注为 0 ~ N-1 的数字。
但是题目用例,第一行给出N=4,但是第五行出现了电脑编号也是4的情况。
这影响到了下面代码中dist、visited数组长度的定义。当前代码实现以用例数据为准,即认为电脑编号是 1~N。
具体考试时需要随机应变。
import Foundation func ODTest_2_49() { print("输入描述") print("第一个参数:局域网内电脑个数N,1 ≤ N ≤ 200;") let n = Int(readLine() ?? "") ?? 0 print("第二个参数:总共多少条网络连接") let m = Int(readLine() ?? "") ?? 0 print("第三个 2 1 1 表示2->1时间为1") var graph: [Int: [[Int]]] = [:] for _ in 0 ..< m { let data = (readLine() ?? "").split(separator: " ").map { Int($0) ?? 0 } let u = data[0] // 出发点 let v = data[1] // 目标点 let w = data[2] // 出发点到达目标点的耗时 var list = graph[u] ?? [] list.append([v, w]) graph[u] = list
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2024华为OD机试卷题 文章被收录于专栏
本专栏给大家提供了华为2024最新华为OD 题目汇总。华为OD机试刷题记录机考算法题库,帮助你上岸华为。提供C++/Java、JavaScript、Python四种语言的解法。