刷题笔记合集🔗

电脑病毒感染

问题描述

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.nextIn