思路：Dijkstra

本题是一道单源最短路的模板题，不太熟悉图论中如何建图的朋友可以参考这篇文章：笔试ACM模式图论建图模版 - 知乎 (zhihu.com)

最终判断是否能从起点出发到达所有的其他点，如果可以，则输出最远距离，如果不可以，则输出-1。

JavaScript代码

const readline = require('readline');

题目描述

​ 一个局域网内有很多台电脑，分别标注为 $1$ ~ $N$ 的数字。相连接的电脑距离不一样，所以感染时间不一样，感染时间用 $t$ 表示. ​ 其中网络内一台电胶被病毒感染，求其感染网络内所有的电脑最少需要多长时间。如果最后有电脑不会感染，则返回 $-1$. ​ 给定一个数组 $times$ 表示一台电脑把相邻电脑感染所用的时间。 如图: $path[i]$ =${i,j,t}$ 表示: 电脑 $i$ -> $j$，电脑 $i$ 上的病毒感染 $j$，需要时间 $t$.

输入描述

第一行输入一个整数 $N$ ，表示局域网内电脑个数 $N$，$1 \le N \le 200$;

第二行输入一个整数 $M$ ,表示有 $M$ 条网络连接；

接下来 $M$行 ,每行输入为 $i , j , t$，代表电脑 $i$ 感染电脑 $j$ 需要时间 $t$。（$1 \le i,j \le 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