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