一. 题目-电脑病毒感染
一个局域网内有很多台电脑，分别标注为0 - N-1的数字。相连接的电脑距离不一样，所以感染时间不一样，感染时间用t表示。
其中网络内一个电脑被病毒感染，其感染网络内所有的电脑需要最少需要多长时间。如果最后有电脑不会感染，则返回-1
给定一个数组times表示一个电脑把相邻电脑感染所用的时间。
如图：path[i]= {i,j, t} 表示电脑i->j 电脑i上的病毒感染j，需要时间t。
输入描述：
4
3
2 1 1
2 3 1
3 4 1
2
输出描述：
2
补充说明：
第一个参数:局域网内电脑个数N 1<=N<=200;
第二个参数：总共多少条网络连接
第三个 1 2 1 表示1->2时间为1
第七行：表示病毒最开始所在的电脑号1
收起
示例1
输入：
4
3
2 1 1
2 3 1
3 4 1
2
输出：
2
二.解题思路
这个问题可以通过使用广度优先搜索（BFS）算法来解决。以下是解题思路：
-
首先，建立一个字典或者列表，用于表示网络连接关系。字典的键是电脑的编号，对应的值是一个列表，列表中包含与该电脑直接相连的电脑及感染所需的时间。
-
初始化一个数组
target，用于存储从起始感染电脑到每个电脑的最短感染时间。将target初始化为正无穷大，表示初始情况下无法感染到其他电脑。将起始感染电脑的target设为0。 -
使用广度优先搜索算法遍历网络，从起始感染电脑开始，逐层感染相邻的电脑，并更新其感染时间。每次选择感染时间最短的电脑进行拓展。
-
最终，找到
target数组中的最大值，即为感染网络内所有电脑所需的最短时间。如果存在无法感染到的电脑，返回-1。
这种方法保证了每个电脑被感染的顺序是按照最短感染时间进行的，从而得到最优解。在代码中，可以使用一个队列来实现广度优先搜索，同时使用一个数组来记录已经访问的电脑，以避免重复访问。
三.题解代码
Python题解代码
import sys
computer_nums = int(sys.stdin.readline().strip())
link_nums = int(sys.stdin.readline().strip())
network = {}
for item in range(link_nums):
line = sys.stdin.readline().strip()
i, j, k = list(map(int, line.split()))
if i in network:
network[i].append([j, k])
else:
network[i] = [[j, k]]
target = [sys.maxsize] * (computer_nums + 1)
source = int(sys.stdin.readline().strip())
target[source] = 0
compare = [source]
vd = [False] * (computer_nums + 1)
vd[source] = True
while len(compare) > 0:
cur = compare.pop()
vd[cur] = False
if network.get(cur):
for i, j in network[cur]:
count = target[cur] + j
if target[i] <= count:
continue
target[i] = count
if vd[i]:
continue
vd[i] = True
compare.append(i)
compare.sort(key=lambda x: -target[x])
result = max(target[1:])
print(-1 if result == sys.maxsize else result)
JAVA题解代码
import java.util.*;
public class Main {
static final int N = 510; // 最大顶点数
static class Edge {
int next, to, weight;
public Edge(int next, int to, int weight) {
this.next = next;
this.to = to;
this.weight = weight;
}
}
static int[] ne = new int[N];
static int[] h = new int[N];
static int[] w = new int[N];
static int[] e = new int[N];
static int idx; // 邻接表表示图，ne数组表示链表中下一个节点的索引，h数组表示每个节点的链表头，w数组表示边的权值，e数组表示边的终点，idx表示当前位置
static int[] dist = new int[N];
static int st, n, m; // dist数组表示从源点到各个节点的距离，st表示源点，n表示节点数，m表示边数
static void add(int a, int b, int c) {
// 添加一条从a到b的权值为c的边到邻接表
ne[idx] = h[a];
e[idx] = b;
w[idx] = c;
h[a] = idx++;
}
static int dijkstra() {
// 使用Dijkstra算法计算单源最短路
PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(arr -> arr[0])); // 使用小顶堆作为优先队列，int[]表示整数对，arr[0]表示距离，arr[1]表示节点
heap.offer(new int[]{0, st}); // 将源点入队，距离为0
while (!heap.isEmpty()) {
int[] t = heap.poll();
int u = t[1], d = t[0];
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
// 如果通过u到j的距离更短
if (dist[j] > d + w[i]) {
dist[j] = d + w[i]; // 更新距离
heap.offer(new int[]{dist[j], j}); // 将新的距离和节点加入优先队列
}
}
}
int res = 0;
for (int i = 1; i <= n; i++) {
res = Math.max(res, dist[i]); // 计算最短路径中的最大值
}
if (res == 0x3f3f3f3f) return -1; // 如果最终的最大距离为无穷大，说明有不可达的节点，返回-1
return res;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt(); // 读入节点数
m = scanner.nextInt(); // 读入边数
Arrays.fill(h, -1); // 初始化邻接表
Arrays.fill(dist, 0x3f3f3f3f); // 初始化距离数组
for (int i = 0; i < m; i++) {
int a = scanner.nextInt(), b = scanner.nextInt(), c = scanner.nextInt();
add(a, b, c); // 建图，添加有向边
}
st = scanner.nextInt(); // 读入源点
dist[st] = 0;
System.out.println(dijkstra()); // 输出最短路径的最大距离
}
}
C/C++题解代码
#include<bits/stdc++.h>
using namespace std;
int bk[205][205];
int n , m;
void init (){
memset(bk , -1 , sizeof(bk));
for (int i = 0 ; i <= n ; i++) bk[i][i] = 0;
}
vector<int> dijstra (int start);
void readEdge (){
for (int i = 0; i < m; i++) {
int x , y , z;
cin >> x >> y >> z;
if (bk[x][y] == -1)
bk[x][y] = z;
else
bk[x][y] = min(bk[x][y] , z);
}
}
int main() {
cin >> n;
cin >> m;
init();
readEdge();
int start;
cin >> start;
vector<int> dis = dijstra(start);
bool ok = true;
int mx = 0;
for (int i = 1; i <= n; i++) {
mx = max(mx , dis[i]);
if (dis[i] == INT_MAX) {
ok = false;
break;
}
}
if (ok) {
cout << mx << endl;
} else {
cout << -1 << endl;
}
return 0;
}
vector<int> dijstra (int start){
vector<int> dis(n + 1 , INT_MAX);
vector<bool> vis(n + 1 , false);
dis[start] = 0;
for (int i = 1; i <= n; i++) {
int minn = INT_MAX;
int u = -1;
for (int j = 1; j <= n; j++) {
if (!vis[j] && dis[j] < minn) {
minn = dis[j];
u = j;
}
}
if (u == -1) break;
vis[u] = true;
for (int j = 1; j <= n; j++) {
if (!vis[j] && bk[u][j] != -1 && dis[u] + bk[u][j] < dis[j]) {
dis[j] = dis[u] + bk[u][j];
}
}
}
return dis;
}
JS题解代码
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let n, m;
let ne, h, w, e, idx, dist;
let st;
function add(a, b, c) {
ne[idx] = h[a];
e[idx] = b;
w[idx] = c;
h[a] = idx++;
}
function dijkstra() {
const heap = [[0, st]];
dist[st] = 0;
while (heap.length > 0) {
heap.sort((a, b) => a[0] - b[0]);
const [d, u] = heap.shift();
if (dist[u] < d) continue;
for (let i = h[u]; i !== -1; i = ne[i]) {
const j = e[i];
if (dist[j] > d + w[i]) {
dist[j] = d + w[i];
heap.push([dist[j], j]);
}
}
}
let res = 0;
for (let i = 1; i <= n; i++) {
res = Math.max(res, dist[i]);
}
return res === 0x3f3f3f3f ? -1 : res;
}
let lineCount = 0;
rl.on('line', (line) => {
lineCount++;
const parts = line.split(' ').map(Number);
if (lineCount === 1) {
n = parts[0];
} else if (lineCount === 2) {
m = parts[0];
ne = new Array(n + 1).fill(0);
h = new Array(n + 1).fill(-1);
w = new Array(n + 1).fill(0);
e = new Array(n + 1).fill(0);
idx = 0;
dist = new Array(n + 1).fill(0x3f3f3f3f);
} else if (lineCount > 2 && lineCount <= m + 2) {
add(parts[0], parts[1], parts[2]);
} else if (lineCount === m + 3) {
st = parts[0];
console.log(dijkstra());
rl.close();
}
});
代码OJ评判结果
通过测试点
四.代码讲解(Java&Python&C++&JS分别讲解)
Python题解代码解析：
-
导入模块： 使用
import sys导入sys模块，该模块提供了对 Python 解释器进行访问的一些变量和函数。 -
读取输入： 使用
sys.stdin.readline().strip()读取标准输入，首先读取局域网内电脑的个数computer_nums和总共的网络连接数link_nums。 -
建立网络连接关系： 使用字典
network表示电脑之间的网络连接关系。通过循环读取每一条网络连接信息，将信息添加到字典中，其中键是电脑的编号，对应的值是一个列表，列表中包含与该电脑直接相连的电脑及感染所需的时间。 -
初始化目标数组： 使用数组
target表示从起始感染电脑到每个电脑的最短感染时间。将数组初始化为正无穷大，表示初始情况下无法感染到其他电脑。将起始感染电脑的目标时间设为0。 -
广度优先搜索： 使用广度优先搜索算法遍历网络，从起始感染电脑开始，逐层感染相邻的电脑，并更新其感染时间。通过队列
compare记录待处理的电脑，使用数组vd记录已经访问的电脑，避免重复访问。 -
结果计算： 最终，找到
target数组中的最大值，即为感染网络内所有电脑所需的最短时间。如果存在无法感染到的电脑，返回-1。最后输出结果。
JAVA题解代码解析：
-
导入包： 使用
import java.util.*;导入 Java 中的util包，该包提供了各种实用工具类。 -
定义 Edge 类： 定义一个
Edge类表示图的边，包括next表示下一个节点的索引，to表示边的终点，weight表示边的权值。 -
初始化图： 使用数组和变量初始化图的相关信息，包括
ne数组表示链表中下一个节点的索引，h数组表示每个节点的链表头，w数组表示边的权值，e数组表示边的终点，idx表示当前位置。 -
添加边的方法： 定义
add方法，用于向图中添加一条从节点a到节点b权值为c的边。 -
Dijkstra算法： 定义
dijkstra方法，使用 Dijkstra 算法计算单源最短路。使用小顶堆作为优先队列，遍历图中的节点，更新最短路径。 -
主函数： 在主函数中，使用
Scanner读取输入，初始化图，并调用dijkstra方法计算最短路径的最大距离。输出结果。
C/C++题解代码解析：
-
初始化： 使用
memset函数将bk数组初始化为 -1，表示初始时没有连接关系。然后使用循环将bk数组的对角线元素设置为0，表示自身到自身的距离为0。 -
读取边的信息： 使用循环读取每条边的信息，将具有最小感染时间的边信息记录到
bk数组中。如果两台电脑之间已有边存在，保留具有最小感染时间的边。 -
Dijkstra算法： 定义
dijkstra函数，实现 Dijkstra 算法。在该函数中，使用优先队列和vis数组记录已访问的节点，更新最短路径。 -
主函数： 在主函数中，读取输入，初始化图，调用
dijkstra函数计算最短路径，判断是否存在不可达的节点，并输出结果。
JS题解代码解析：
-
引入readline模块： 使用
const readline = require('readline');引入 Node.js 中的readline模块，该模块提供了一组接口，用于从可读流（如process.stdin）读取数据。 -
初始化变量： 初始化输入、图的相关变量，包括节点数
n、边数m、邻接表和其他辅助数组。 -
添加边的函数： 定义
add函数，用于向图中添加一条从节点a到节点b权值为c的边。 -
Dijkstra算法： 定义
dijkstra函数，使用小顶堆实现 Dijkstra 算法，计算单源最短路。在该函数中，更新最短路径。 -
读取输入并执行算法： 使用
rl.on('line', (line) => {...});监听每行输入，根据输入执行相应的操作，包括初始化图、读取边的信息、调用dijkstra函数计算最短路径，最后输出结果。
以上代码主要涉及图的建立和最短路径算法的实现，分别使用了不同的语言特性和库来完成相应的任务。