最新华为OD机试真题-电脑病毒感染(200分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新 华为OD机试-D卷 的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> 电脑病毒感染(200分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

💊 电脑病毒感染

问题描述

K小姐是一家公司的网络管理员，最近她发现公司内部的局域网出现了电脑病毒。经过调查，K小姐了解到病毒是从某一台电脑开始传播的，通过电脑之间的网络连接，病毒会感染其他电脑。

公司内部一共有 台电脑，编号从 到 。电脑之间存在 条网络连接，每条连接由三个整数 表示，意味着电脑 和电脑 之间存在网络连接，如果电脑 感染了病毒，那么经过时间 后，电脑 也会被感染。

现在，K小姐知道最开始病毒是从编号为 的电脑开始传播的。她想知道，最少需要多长时间，病毒才能感染所有的电脑。如果无法感染所有电脑，则输出 。

输入格式

第一行包含两个整数 和 ，表示电脑数量和网络连接数量。

接下来 行，每行包含三个整数 ，表示电脑 和电脑 之间的网络连接以及传播时间 。

最后一行包含一个整数 ，表示最初感染病毒的电脑编号。

输出格式

输出一个整数，表示病毒传播到所有电脑所需的最短时间。如果无法感染所有电脑，则输出 。

样例输入

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

样例输出

2

数据范围

题解

本题可以使用 Dijkstra 算法求解最短路径问题。从初始感染病毒的电脑出发，将其到其他所有电脑的最短感染时间求出来，然后取其中的最大值即可。

• 初始化距离数组 ，将初始感染电脑的距离设为 ，其他电脑的距离设为正无穷。
• 使用优先队列进行 Dijkstra 算法，每次取出距离最小的电脑，更新其相邻电脑的距离。
• 遍历所有电脑，找出最大的距离值，即为最短感染时间。如果存在无穷大的距离，说明无法感染所有电脑，返回 。

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

import heapq

N = 210
INF = 0x3f3f3f3f

if __name__ == "__main__":
    n = int(input())
    m = int(input())
    edges = [[] for _ in range(N)]
    dist = [INF] * N

    for _ in range(m):
        a, b, w = map(int, input().split())
        edges[a].append((b, w))

    start = int(input())
    dist[start] = 0

    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in edges[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

    res = max(dist[1:n+1])
    print(res if res < INF else -1)

• Java

import java.util.*;

public class Main {
    static int N = 210;
    static int INF = 0x3f3f3f3f;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        List<int[]>[] edges = new List[N];
        for (int i = 0; i < N; i++) {
            edges[i] = new ArrayList<>();
        }
        int[] dist = new int[N];
        Arrays.fill(dist, INF);

        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int w = sc.nextInt();
            edges[a].add(new int[]{b, w});
        }

        int start = sc.nextInt();
        dist[start] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, start});
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0], u = curr[1];
            if (d > dist[u]) {
                continue;
            }
            for (int[] edge : edges[u]) {
                int v = edge[0], w = edge[1];
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }

        int res = 0;
        for (int i = 1; i <= n; i++) {
            res = Math.max(res, dist[i]);
        }
        System.out.println(res < INF ? res : -1);
    }
}

• Cpp

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int N = 210;
const int INF = 0x3f3f3f3f;

vector<pair<int, int>> edges[N];
int dist[N];

int main() {
    int n, m;
    cin >> n >> m;

    fill(dist, dist + N, INF);

    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        edges[a].push_back({b, w});
    }

    int start;
    cin >> start;
    dist[start] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) {
            continue;
        }
        for (auto [v, w] : edges[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i++) {
        res = max(res, dist[i]);
    }
    cout << (res < INF ? res : -1) << endl;

    return 0;
}