华为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