本题是一道单源最短路的模板题,不太熟悉图论中如何建图的朋友可以参考这篇文章:笔试ACM模式图论建图模版 - 知乎 (zhihu.com)
最终判断是否能从起点出发到达所有的其他点,如果可以,则输出最远距离,如果不可以,则输出-1。
const readline = require('readline');
一个局域网内有很多台电脑,分别标注为 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;
输入
4
3
2 1 1
2 3 1
3 4 1
2
输出
2
说明
第一个参数:局域网内电脑个数N,1 ≤ N ≤ 200;
第二个参数:总共多少条网络连接
第三个 2 1 1 表示2->1时间为1
第六行:表示病毒最开始所在电脑号2