最新华为OD机试真题-电脑病毒感染(200分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新 华为OD机试-D卷 的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
📎在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓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;
}
#华为##华为OD##华为OD题库##秋招##笔试#最新华为OD机试-D卷 文章被收录于专栏
本专栏给大家提供了华为2024最新华为OD-C/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 提供OJ在线评测