Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!