#P3267. 电脑病毒感染(200分)
-
1000ms
Tried: 122
Accepted: 34
Difficulty: 7
所属公司 :
华为od
电脑病毒感染(200分)
思路:Dijkstra
本题是一道单源最短路的模板题,不太熟悉图论中如何建图的朋友可以参考这篇文章:笔试ACM模式图论建图模版 - 知乎 (zhihu.com)
最终判断是否能从起点出发到达所有的其他点,如果可以,则输出最远距离,如果不可以,则输出-1。
JavaScript代码
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();
}
});
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()); // 输出最短路径的最大距离
}
}
Python代码
import heapq
N = 510 # 定义一个常量 N,表示数组大小
class Pair:
def __init__(self, x, y):
self.x = x # Pair 的第一个元素
self.y = y # Pair 的第二个元素
def __lt__(self, other):
return self.x < other.x # 定义 Pair 对象之间的小于比较,用于堆的排序
ne = [0] * N # 邻接表的指针数组,记录每个点的第一条边在 e 数组中的位置
h = [-1] * N # 邻接表的头指针数组,记录每个点的第一条边的位置
w = [0] * N # 边的权值数组
e = [0] * N # 边的终点数组
idx = 0 # 边的数量
dist = [0x3f3f3f3f] * N # 距离数组,用于记录起点到各点的最短距离,初始化为无穷大
st = 0 # 起点
n = 0 # 点的数量
m = 0 # 边的数量
def add(a, b, c):
global idx # 使用全局变量
ne[idx] = h[a]
e[idx] = b
w[idx] = c
h[a] = idx
idx += 1
def dijkstra():
global st # 使用全局变量
heap = [Pair(0, st)] # 优先队列,存储 Pair 对象,用于贪心选择最短距离的点
dist[st] = 0 # 起点到自身的距离为 0
while heap:
t = heapq.heappop(heap) # 弹出堆顶元素,即当前距离起点最近的点
u, d = t.y, t.x
i = h[u]
while i != -1:
j = e[i]
if dist[j] > d + w[i]: # 更新距离数组
dist[j] = d + w[i]
heapq.heappush(heap, Pair(dist[j], j)) # 将更新后的距离和点加入堆中
i = ne[i]
res = 0
for i in range(1, n + 1):
res = max(res, dist[i]) # 找到最长的最短距离,即答案
if res == 0x3f3f3f3f:
return -1
return res
if __name__ == "__main__":
n = int(input()) # 读入点的数量
m = int(input()) # 读入边的数量
h = [-1] * N # 初始化邻接表的头指针数组
dist = [0x3f3f3f3f] * N # 初始化距离数组
for _ in range(m):
a, b, c = map(int, input().split())
add(a, b, c) # 添加边到邻接表
st = int(input()) # 读入起点
print(dijkstra()) # 输出结果
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;
}
题目描述
一个局域网内有很多台电脑,分别标注为 1 ~ N 的数字。相连接的电脑距离不一样,所以感染时间不一样,感染时间用 t 表示. 其中网络内一台电胶被病毒感染,求其感染网络内所有的电脑最少需要多长时间。如果最后有电脑不会感染,则返回 −1. 给定一个数组 times 表示一台电脑把相邻电脑感染所用的时间。 如图: path[i] =i,j,t 表示: 电脑 i -> j,电脑 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
说明
第一个参数:局域网内电脑个数N,1 ≤ N ≤ 200;
第二个参数:总共多少条网络连接
第三个 2 1 1 表示2->1时间为1
第六行:表示病毒最开始所在电脑号2