1711: 限制距离内邻居最多的城堡

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:10 解决:8

题目描述

有 n 个城堡,按从 0 到 n-1 编号。k条边(双向加权边)和一个最大距离s

返回能通过某些边到达其他城堡数目最多、且距离 最大 为 s 的 城堡。如果有多个这样的城堡,则返回编号最大的城堡。


示例:n=5,k=6,s=3

各城堡分别能到:

城堡0:2

城堡1:2,3,4

城堡2:0,1,4

城堡3:1,4

城堡4:1,2,3

城堡1,2,4都能到三个城堡,但是编号最大的城堡是4,所以应该返回城堡4

输入

第一行三个整数n,k,s,分别表示城堡e数,边数,距离最大值

接下来有k行,每行三个数v,e,w,分别表示v到e之间有一条权值为w的边

输出

输出能到城堡最多并且距离最大为s的城堡编号

样例输入 复制

5 6 3
0 1 5
1 3 1
1 4 1
3 4 3
0 2 2
4 2 2

样例输出 复制

4