华为OD机试 - 电脑病毒感染 - 最短路径问题(Java 2024 C卷 200分)
华为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。
具体步骤
- 初始化图:使用邻接矩阵或邻接表表示图。
- Dijkstra 算法:从源节点开始,计算到所有其他节点的最短路径。
- 处理不可达节点:如果有节点在 Dijkstra 算法完成后仍然是无穷大路径,说明它不可达。
- 计算最大感染时间:所有电脑都可达时,最长的最短路径即为感染全部电脑所需的最短时间。
五、Java算法源码
public class OdTest01 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt(); // 电脑数量
int M = scanner.nextInt(); // 连接数量
// 使用一个大值初始化邻接矩阵,表示无连接
int[][] graph = new int[N + 1][N + 1];
for (int[] row : graph) {
Arrays.fill(row, Integer.MAX_VALUE / 2); // 防止后续运算溢出
}
for (int i = 0; i < M; i++) {
int u = scanner.nextInt();
int v = scanner.nextInt();
int t = scanner.nextInt();
graph[u][v] = Math.min(graph[u][v], t); // 可能有重复边,取最小值
}
int start = scanner.nextInt(); // 病毒所在电脑编号
// 使用Dijkstra算法找到从起点到所有点的最短路径
int[] minTime = dijkstra(graph, N, start);
// 找到最大的最短路径时间,如果有电脑不可达,则返回-1
int maxTime = 0;
for (int i = 1; i <= N; i++) {
if (minTime[i] == Integer.MAX_VALUE / 2) {
System.out.println(-1);
return;
}
maxTime = Math.max(maxTime, minTime[i]);
}
System.out.println(maxTime);
}
private static int[] dijkstra(int[][] graph, int N, int start) {
int[] dist = new int[N + 1];
boolean[] visited = new boolean[N + 1];
Arrays.fill(dist, Integer.MAX_VALUE / 2);
dist[start] = 0;
for (int i = 0; i < N; i++) {
int u = -1;
int minDist = Integer.MAX_VALUE / 2;
for (int j = 1; j <= N; j++) {
if (!visited[j] && dist[j] < minDist) {
u = j;
minDist = dist[j];
}
}
if (u == -1) break; // 所有可达节点都已访问
visited[u] = true;
for (int v = 1; v <= N; v++) {
if (graph[u][v] != Integer.MAX_VALUE / 2 && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
return dist;
}
}
六、效果展示
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在线答疑。
还没有评论,来说两句吧...