1211: 路由时间

题目描述

有n个路由器，标记为1到n。现有一个延迟时间列表times, 表示消息在路由器之间传递所需的时间。$times[i] = (u_i,v_i,w_i)$，其中$u_i$为源节点，$v_i$是目标节点，$w_i$表示从$u_i$到$v_i$所需的时间。问从某路由器k发出一条消息，需要多久所有路由器都能接收到消息。如果不能接收到消息，返回-1.

输入格式

第一行为三个数n，m和k，分别表示路由器个数，边的个数和从k路由器发出消息。
接下来m行，表示$(u_i,v_i,w_i)$。

输出格式

需要的时间或-1。

样例输入

input 1

4 3 2
2 1 1
2 3 1
3 4 1

input 2

2 1 1
1 2 1

input 3

2 1 2
1 2 1

样例输出

output 1

2

output 2

1

output 3

-1

数据范围

1<=k<=n<=100

0<=$w_i$ <=100

所有$(u_i,v_i)$对均不相同，即不含重复边。

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！