列表

详情


NC54783. 小民与散步

描述

众所周知,民大景色优美。小民很喜欢在校园里散步。
校园内有n栋建筑,某些建筑间有双向道路连接,道路总共有m条。路边绿树成荫、花鸟成群,所以小民走在道路上时,不会折返,一定会走到终点。
现在小民从宿舍出发,他想走至少k分钟,同时尽可能地减少经过的道路条数,并最终首次回到宿舍。途中,只要满足他对路径的要求,小民可以选择连接他所在建筑的任意道路行走。
小民想知道满足他要求的最少的道路条数。

输入描述

第一行包含3个整数n m k,含义见题
接下来包含m行,每行3个整数u v w,表示存在一条连接标号u的建筑与标号v的建筑的道路,需要w分钟走完
(宿舍的标号为1;两个建筑间可能存在多条道路;可能存在起终点一致的道路)


输出描述

输出一行一个整数,表示满足条件的路径的最少道路条数

如果不存在这样的路径,输出-1

示例1

输入:

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

输出:

4

说明:

1->2

2->3

3->2

2->1

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

上一题