OD C卷 - 电脑病毒感染

电脑病毒感染（200）

一个局域网内有n台电脑，编号为 1 -> n，电脑之间病毒感染时间用 t 表示；
现在网络内已有一台电脑被病毒感染，求其感染所有其他电脑最少的时间，若最后有电脑不会被感染，则返回-1;
数组times 表示已感染电脑把相邻的电脑感染所用的时间，path[i] = {i, j, t} 表示电脑编号为i 感染电脑编号j 所用的时间t;

输入描述：
第一行输入n（台电脑），范围在[1, 200]
第二行输入m, 表示 m 条（有向）网络（只能通过该有向网络才可以感染）；
随后的 m 行，每行输入 i, j, t, 1<=i, j<=n
最后一行输入携带病毒的电脑编号（>=1）；

输出描述：
感染全部电脑的最少时间，若不能感染全部，则输出 -1

示例1
输入：
4
3
2 1 1
2 3 1
3 4 1
2
输出：
2

示例2
输入
4
4
1 2 2
2 3 1
3 4 10
2 4 3
2
输出：
-1

思路：

times数组表示每台电脑被感染的时间，未感染时为float(‘inf’)；
通过m条有向网络传播感染，不断更新每台电脑感染的最少时间；

 
# 输入电脑数
n = int(input().strip())
# 每台电脑的感染时间
times = [float('inf') for _ in range(n)]# 输入 有向网络 的条数
m = int(input().strip())# m * 3 的矩阵  每一行表示一条有向网络
matrix = []
for i in range(m):matrix.append([int(x) for x in input().strip().split()])# 输入带有病毒的电脑编号
start = int(input().strip())
start_idx = start - 1
# 起始的带有病毒的电脑 感染时间为0
times[start_idx] = 0# 通过 有向网络 感染
for j in range(m):from_pid = matrix[j][0] - 1to_pid = matrix[j][1] - 1cur_t = matrix[j][2]use_t = times[from_pid] + cur_t# 更新 被感染电脑的更少的时间if times[to_pid] > use_t:times[to_pid] = use_t# 输出结果
result = 0
i = 0
label = False
while i < n:if times[i] == float('inf'):label = Truebreakif times[i] > result:result = times[i]i += 1if label:print(-1)
else:print(result)