专栏名称: 吴师兄学算法
和程序员小吴一起从初学者的角度学习算法，以动画的形式呈现解题的思路。每周四篇原创文章，期待你的鉴赏！
目录
相关文章推荐
FM1007福建交通广播  ·  宇树科技携两款机器人亮相2025GDC ·  7 小时前  
FM1007福建交通广播  ·  宇树科技携两款机器人亮相2025GDC ·  7 小时前  
中国航务周刊  ·  三大航运巨头MSC、马士基、达飞，抢占这一重 ... ·  2 天前  
中国航务周刊  ·  MSC两条远洋干线，在大连港首航！ ·  3 天前  
中国航务周刊  ·  【展商推介】星亚航运，邀您莅临“2025国际 ... ·  4 天前  
中国航务周刊  ·  中远海控首制，国内首艘！ ·  3 天前  
51好读  ›  专栏  ›  吴师兄学算法

华为笔试，拿下！

吴师兄学算法  · 公众号  ·  · 2024-09-09 20:56

正文

大家好，我是吴师兄。

今天继续来一道和「大厂秋招」相关的算法原题。

2024 年的大厂真题可以在我的网站上进行练习。

网站地址： https://oj.algomooc.com/

题目描述

一个局域网内有很多台电脑，分别标注为 0 到 N-1 的数字。

相连接的电脑距离不一样，所以感染时间不一样，感染时间用 t 表示。

其中网络内一个电脑被病毒感染，其感染网络内所有的电脑需要最少需要多长时间。如果最后有电脑不会感染，则返回 -1 。

给定一个数组 times 表示一个电脑把相邻电脑感染所用的时间。

path[]= {i,j,t} 表示电脑 i->j 电脑 i 上的病毒感染 j ，需要时间 t 。

输入描述

第一行一个参数，表示局域网内电脑个数 N 。 1<=N<=200

第二行一个参数，表示网络连接条数 M

接下来 M 行，表示网络连接情况，格式为 i j t

最后一行一个参数，表示病毒最开始所在的电脑编号

输出描述

一个数字，表示感染电脑所需要花费的所有时间。

示例

输入 

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

输出 

2

解题思路

Dijkstra最短路问题板子题。本题和LeetCode743、网络延迟时间 几乎完全一致。

注意，题目中虽然说节点编号是 0 到 N-1 ，但是从示例和题目结果上来看编号 1 到 N 。这属于题目本身出题的不眼睛。

Dijkstra算法的具体介绍详见 最短路问题Dijkstra算法专题）

代码

解法一：数组构建dist

Python 



from collections import defaultdict
from heapq import heappush, heappop
INF = 100000

# 节点数
n = int(input())
# 边数
m = int(input())
# 用一个哈希表，储存有向图边连接情况
neighbor_dic = defaultdict(list)
# 循环m次，表示m条边
for _ in range(m):
    # a->b花费时间t
    a, b, t = map(int, input().split())
    # 储存数据
    neighbor_dic[a].append((b, t))
# 输入初始节点
start = int(input())

# 初始化dist数组
dist = [INF] * (n+1)

# 初始化一个最小堆，其中储存起始点start
# 每个元素都是一个二元组，
# 其中第一个元素是时间，第二个元素是节点编号
heap = [(0, start)]


# 进行Dijkstra（类似BFS）
while heap:
    # 从堆中弹出当前时间最小的节点
    # 得到节点编号cur_node，该节点对应的时间cur_time
    cur_time, cur_node = heappop(heap)

    # 如果当前节点的已记录最短时间比当前时间更小，说明已经找到更优的路径
    # 因此可以跳过当前节点
    if cur_time > dist[cur_node]:
        continue

    # 更新从源节点start到当前节点cur_node的最短时间
    dist[cur_node] = cur_time

    # 遍历当前节点cur_node的所有相邻节点
    # next_node是下一个节点编号，next_weight是从cur_node到next_node所花费的时间
    for next_node, next_weight in neighbor_dic[cur_node]:
        # 计算通过当前节点cur_node到达相邻节点next_node所需的时间
        next_time = cur_time + next_weight

        # 如果通过当前节点到达相邻节点的时间比之前记录的最短时间更短
        # 则更新相邻节点的最短时间，并将其加入堆中以便进一步探索
        if next_time             heappush(heap, (next_time, next_node))


# 计算dist数组中的最大值，注意节点编号是1到N，所以dist要从1开始取切片
# 如果最大值仍为INF，说明有些节点达不到，应该输出-1
# 否则输出ans，作为感染所有节点需要花费的总时间
ans = max(dist[1:])
print(ans if ans else -1)

Java 

import java.util.*;

public class Main {
    static final int INF = 100000




    
;  // 用于表示一个非常大的数，作为初始的最短距离

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入节点数
        int n = scanner.nextInt();
        // 输入边数
        int m = scanner.nextInt();

        // 用一个哈希表，储存有向图边连接情况
        Mapint[]>> neighbor_dic = new HashMap<>();

        // 循环m次，表示m条边
        for (int i = 0; i             int a = scanner.nextInt();  // 起点
            int b = scanner.nextInt();  // 终点
            int t = scanner.nextInt();  // 边权重
            // 如果节点a尚未有邻接节点列表，则创建一个新的列表
            neighbor_dic.putIfAbsent(a, new ArrayList<>());
            // 储存数据
            neighbor_dic.get(a).add(new int[]{b, t});
        }

        // 输入初始节点
        int start = scanner.nextInt();

        // 初始化dist数组
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INF);  // 设置所有节点的初始距离为INF

        // 初始化一个最小堆，其中储存起始点start
        // 每个元素都是一个二元组，
        // 其中第一个元素是时间，第二个元素是节点编号
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        heap.offer(new int[]{0, start});

        // 进行Dijkstra算法（类似BFS）
        while (!heap.isEmpty()) {
            // 从堆中弹出当前时间最小的节点
            int[] current = heap.poll();
            int cur_time = current[0];
            int cur_node = current[1];

            // 如果当前节点的已记录最短时间比当前时间更小，说明已经找到更优的路径
            // 因此可以跳过当前节点
            if (cur_time > dist[cur_node]) {
                continue;
            }

            dist[cur_node] = cur_time;

            // 遍历当前节点cur_node的所有相邻节点
            for (int[] neighbor : neighbor_dic.getOrDefault(cur_node, new ArrayList<>())) {
                int next_node = neighbor[0];
                int next_weight = neighbor[1];
                // 计算通过当前节点cur_node到达相邻节点next_node所需的时间
                int next_time = cur_time + next_weight;

                // 如果通过当前节点到达相邻节点的时间比之前记录的最短时间更短
                // 则更新相邻节点的最短时间，并将其加入堆中以便进一步探索
                if (next_time                     heap.offer(new int[]{next_time, next_node});
                }
            }
        }

        // 计算dist数组中的最大值，注意节点编号是1到n，所以dist要从1开始取切片
        // 如果最大值仍为INF，说明有些节点达不到，应该输出-1
        // 否则输出ans，作为感染所有节点需要花费的总时间
        int ans = Arrays.stream(dist, 1, n + 1).max().getAsInt();
        System.out.println(ans 1);

        scanner.close();
    }
}

C++ 

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int INF = 100000;  // 用于表示一个非常大的数，作为初始的最短距离

int main() {
    int n, m;
    // 输入节点数
    cin >> n;
    // 输入边数
    cin >> m;

    // 用一个哈希表，储存有向图边连接情况
    unordered_map<int, vectorint, int>>> neighbor_dic;

    // 循环m次，表示m条边
    for (int i = 0; i         int a, b, t;
        // a->b花费时间t
        cin >> a >> b >> t;
        // 如果节点a尚未有邻接节点列表，则创建一个新的列表
        neighbor_dic[a].emplace_back(b, t);
    }

    // 输入初始节点
    int start;
    cin >> start;

    // 初始化dist数组
    vector<int> dist(n + 1, INF);  // 设置所有节点的初始距离为INF

    // 初始化一个最小堆，其中储存起始点start
    // 每个元素都是一个二元组，
    // 其中第一个元素是时间，第二个元素是节点编号
    priority_queueint, int>, vectorint, int>>, greaterint, int>>> heap;
    heap.push({0, start});

    // 进行Dijkstra算法（类似BFS）
    while (!heap.empty()) {
        // 从堆中弹出当前时间最小的节点
        int cur_time = heap.top().first;
        int cur_node = heap.top().second;
        heap.pop();

        // 如果当前节点的已记录最短时间比当前时间更小，说明已经找到更优的路径
        // 因此可以跳过当前节点
        if (cur_time > dist[cur_node]) {
            continue;
        }

        dist[cur_node] = cur_time;

        // 遍历当前节点cur_node的所有相邻节点
        for (auto& neighbor : neighbor_dic[cur_node]) {
            int next_node = neighbor.first;
            int next_weight = neighbor.second;
            // 计算通过当前节点cur_node到达相邻节点next_node所需的时间
            int next_time = cur_time + next_weight;

            // 如果通过当前节点到达相邻节点的时间比之前记录的最短时间更短
            // 则更新相邻节点的最短时间，并将其加入堆中以便进一步探索
            if (next_time                 heap.push({next_time, next_node});
            }
        }
    }

    // 计算dist数组中的最大值，注意节点编号是1到n，所以dist要从1开始取
    // 如果最大值仍为INF，说明有些节点达不到，应该输出-1
    // 否则输出ans，作为感染所有节点需要花费的总时间
    int ans = *max_element(dist.begin() + 1, dist.end());
    cout <-1) 
    return 0;
}

解法二：哈希表构建dist

Python 

from collections import defaultdict
from heapq import heappush, heappop

# 用于表示一个非常大的数，作为初始的最短距离
INF = 100000        

# 节点数
n = int(input())
# 边数
m = int(input())
# 用一个哈希表，储存有向图边连接情况
neighbor_dic = defaultdict(list)
# 循环m次，表示m条边
for _ in range(m):
    # a->b花费时间t
    a, b, t = map(int, input().split())
    # 储存数据
    neighbor_dic[a].append((b, t))
# 输入初始节点
start = int(input())

# 初始化dist哈希表
dist = defaultdict(lambda: INF)

# 初始化一个最小堆，其中储存起始点start
# 每个元素都是一个二元组，
# 其中第一个元素是时间，第二个元素是节点编号
heap = [(0, start)]

# 进行Dijkstra（类似BFS）
while heap:
    # 从堆中弹出当前时间最小的节点
    # 得到节点编号cur_node，该节点对应的时间cur_time
    cur_time, cur_node = heappop(heap)

    # 如果当前节点的已记录最短时间比当前时间更小，说明已经找到更优的路径
    # 因此可以跳过当前节点
    if cur_time > dist[cur_node]:
        continue

    # 更新从源节点start到当前节点cur_node的最短时间
    dist[cur_node] = cur_time

    # 遍历当前节点cur_node的所有相邻节点
    # next_node是下一个节点编号，next_weight是从cur_node到next_node所花费的时间
    for next_node, next_weight in neighbor_dic[cur_node]:
        # 计算通过当前节点cur_node到达相邻节点next_node所需的时间
        next_time = cur_time + next_weight

        # 如果通过当前节点到达相邻节点的时间比之前记录的最短时间更短
        # 则更新相邻节点的最短时间，并将其加入堆中以便进一步探索
        if next_time             heappush(heap, (next_time, next_node))

# 如果dist的长度小于n，则说明存在某些节点是无法到达的，应该返回-1
# 否则得到dist中所有值的最大值，作为感染所有节点需要花费的总时间
print(max(dist.values())) if len(dist) == n else print(-1)

Java 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 节点数
        int n = scanner.nextInt();
        // 边数
        int m = scanner.nextInt();

        // 用一个哈希表，储存有向图边连接情况
        Mapint[]>> neighbor_dic = new HashMap<>();

        // 循环m次，表示m条边
        for (int i = 0; i             // a->b花费时间t
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int t = scanner.nextInt();
            // 如果节点a尚未有邻接节点列表，则创建一个新的列表
            neighbor_dic.putIfAbsent(a, new ArrayList<>());
            // 储存数据
            neighbor_dic.get(a).add(new int[]{b, t});
        }

        // 输入初始节点
        int start = scanner.nextInt();

        // 初始化dist哈希表，默认所有节点距离源点为INF
        Map dist = new HashMap<>();

        // 初始化一个最小堆，其中储存起始点start
        // 每个元素都是一个二元组，
        // 其中第一个元素是时间，第二个元素是节点编号
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        heap.offer(new int[]{0, start});

        // 进行Dijkstra算法（类似BFS）
        while (!heap.isEmpty()) {
            // 从堆中弹出当前时间最小的节点
            int[] current = heap.poll();
            int cur_time = current[0];
            int cur_node = current[1];

            // 如果当前节点的已记录最短时间比当前时间更小，说明已经找到更优的路径
            // 因此可以跳过当前节点
            // dist中不包含cur_node的话（认为是INF），则说明尚未访问过
            if (dist.containsKey(cur_node) && cur_time > dist.get(cur_node)) {
                continue;
            }

            // 更新从源节点start到当前节点cur_node的最短时间
            dist.put(cur_node, cur_time);

            // 遍历当前节点cur_node的所有相邻节点
            for (int[] neighbor : neighbor_dic.getOrDefault(cur_node, new ArrayList<>())) {
                int next_node = neighbor[0];
                int next_weight = neighbor[1];
                // 计算通过当前节点cur_node到达相邻节点next_node所需的时间
                int next_time = cur_time + next_weight;

                // 如果通过当前节点到达相邻节点的时间比之前记录的最短时间更短
                // 则更新相邻节点的最短时间，并将其加入堆中以便进一步探索
                if (!dist.containsKey(next_node) || next_time                     dist.put(next_node, next_time);






请到「今天看啥」查看全文


推荐文章
FM1007福建交通广播  ·  宇树科技携两款机器人亮相2025GDC
7 小时前
FM1007福建交通广播  ·  宇树科技携两款机器人亮相2025GDC
7 小时前
中国航务周刊  ·  三大航运巨头MSC、马士基、达飞，抢占这一重要市场！
2 天前
中国航务周刊  ·  MSC两条远洋干线，在大连港首航！
3 天前
中国航务周刊  ·  【展商推介】星亚航运，邀您莅临“2025国际港航物流展”2-B583展位，合作共赢！
4 天前
中国航务周刊  ·  中远海控首制，国内首艘！
3 天前
灼见  ·  他是北航硕士，曾考进北大光华，却因为帆船改写人生，远洋航行至今未归……
8 年前
墨香中华  ·  你是别人的风景，却看湿了我的眼
7 年前
视觉艺术摄影  ·  25 张大师级摄影师拍的照片，美翻了
7 年前
克而瑞地产研究  ·  4月东北、西南城市房价大涨，38城二手房价涨幅持续扩大
7 年前
我要WhatYouNeed  ·  很羡慕高考的人，因为以后好多的坎都不会再有倒计时和提醒了。
7 年前
Sov5搜索   ·   小百科   ·   今天看啥   ·   移动版
51好读 - 好文章就要读起来!