华为OD机试 - 电脑病毒感染 - 最短路径问题(Java 2024 C卷 200分)

叁歲伎倆 2024-05-28 10:25 78阅读 0赞

在这里插入图片描述

华为OD机试 2024C卷题库疯狂收录中,刷题点这里

专栏导读

本专栏收录于《华为OD机试(JAVA)真题(A卷+B卷+C卷)》。

刷的越多,抽中的概率越大,每一题都有详细的答题思路、详细的代码注释、样例测试,发现新题目,随时更新,全天CSDN在线答疑。

一、题目描述

一个局域网只内有很多台电脑,分别标注为 1 ~ N 的数字。相连接的电脑距离不一样,所以感染时间不一样,感染时间用t 表示。

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

给定一个数组 times 表示一台电脑把相邻电脑感染所用的时间: path[i] = {i, j, t} 表示: 电脑i 上的病毒感染 j,需要时间 t 。

二、输入描述

第一行输入一个整数N,表示局域网内电脑个数 N,1<= N<= 200 ;

第二行输入一个整数M, 表示有 M 条网络连接;

接下来M行, 每行输入为 i,j,t 。表示电脑 i 感染电脑 j 需要时间t。(1 <= i, j <= N)

最后一行为病毒所在的电脑编号。

三、输出描述

输出最少需要多少时间才能感染全部电脑,如果不存在输出 -1

1、输入

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

2、输出

2

在这里插入图片描述

四、解题思路

这是一个经典的图中的单源最短路径问题,其中节点是电脑,边是电脑间的连接,边的权重是感染时间。可以使用 Dijkstra 算法来解决这个问题,找出从源节点(初始感染的电脑)到所有其他节点的最短路径。此外,我们需要考虑图可能是不连通的情况,如果存在某些节点不可达,则应返回 -1。

具体步骤

  1. 初始化图:使用邻接矩阵或邻接表表示图。
  2. Dijkstra 算法:从源节点开始,计算到所有其他节点的最短路径。
  3. 处理不可达节点:如果有节点在 Dijkstra 算法完成后仍然是无穷大路径,说明它不可达。
  4. 计算最大感染时间:所有电脑都可达时,最长的最短路径即为感染全部电脑所需的最短时间。

五、Java算法源码

  1. public class OdTest01 {
  2. public static void main(String[] args) {
  3. Scanner scanner = new Scanner(System.in);
  4. int N = scanner.nextInt(); // 电脑数量
  5. int M = scanner.nextInt(); // 连接数量
  6. // 使用一个大值初始化邻接矩阵,表示无连接
  7. int[][] graph = new int[N + 1][N + 1];
  8. for (int[] row : graph) {
  9. Arrays.fill(row, Integer.MAX_VALUE / 2); // 防止后续运算溢出
  10. }
  11. for (int i = 0; i < M; i++) {
  12. int u = scanner.nextInt();
  13. int v = scanner.nextInt();
  14. int t = scanner.nextInt();
  15. graph[u][v] = Math.min(graph[u][v], t); // 可能有重复边,取最小值
  16. }
  17. int start = scanner.nextInt(); // 病毒所在电脑编号
  18. // 使用Dijkstra算法找到从起点到所有点的最短路径
  19. int[] minTime = dijkstra(graph, N, start);
  20. // 找到最大的最短路径时间,如果有电脑不可达,则返回-1
  21. int maxTime = 0;
  22. for (int i = 1; i <= N; i++) {
  23. if (minTime[i] == Integer.MAX_VALUE / 2) {
  24. System.out.println(-1);
  25. return;
  26. }
  27. maxTime = Math.max(maxTime, minTime[i]);
  28. }
  29. System.out.println(maxTime);
  30. }
  31. private static int[] dijkstra(int[][] graph, int N, int start) {
  32. int[] dist = new int[N + 1];
  33. boolean[] visited = new boolean[N + 1];
  34. Arrays.fill(dist, Integer.MAX_VALUE / 2);
  35. dist[start] = 0;
  36. for (int i = 0; i < N; i++) {
  37. int u = -1;
  38. int minDist = Integer.MAX_VALUE / 2;
  39. for (int j = 1; j <= N; j++) {
  40. if (!visited[j] && dist[j] < minDist) {
  41. u = j;
  42. minDist = dist[j];
  43. }
  44. }
  45. if (u == -1) break; // 所有可达节点都已访问
  46. visited[u] = true;
  47. for (int v = 1; v <= N; v++) {
  48. if (graph[u][v] != Integer.MAX_VALUE / 2 && dist[u] + graph[u][v] < dist[v]) {
  49. dist[v] = dist[u] + graph[u][v];
  50. }
  51. }
  52. }
  53. return dist;
  54. }
  55. }

六、效果展示

1、输入

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

2、输出

-1

3、说明

在这里插入图片描述

?下一篇:华为OD机试 - 简易内存池 - 逻辑分析(Java 2024 C卷 200分)

?本文收录于,华为OD机试(JAVA)真题(A卷+B卷+C卷)

刷的越多,抽中的概率越大,每一题都有详细的答题思路、详细的代码注释、样例测试,发现新题目,随时更新,全天CSDN在线答疑。

在这里插入图片描述

发表评论

表情:
评论列表 (有 0 条评论,78人围观)

还没有评论,来说两句吧...

相关阅读