华为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四种语言的解法。

全部评论

相关推荐

昨天 11:42
江西农业大学 C++
点赞 评论 收藏
分享
程序员小白条:你是沟通了900个,不是投了900份简历,你能投900份,意味着对面都要回复你900次,你早就找到实习了,没亮点就是这样的,别局限地区,时间投的也要早,现在都要7月了
点赞 评论 收藏
分享
评论
1
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务