九度Online Judge

OJ新增积分机制,如有任何问题或者建议,请发帖到九度论坛OJ意见反馈版,祝大家一切顺利!
亲,九度OJ官方微博开通了,欢迎你来粉!微博地址:weibo.com/jobdu

 题目1539-九度Online Judge,用代码记录你的成长之路!

题目1539:师弟

时间限制:1 秒

内存限制:128 兆

特殊判题:

提交:275

解决:60

题目描述:

开学了,GrassLand的新师弟也来了,于是GrassLand打算去路口接他,以表兄长之谊。
已知:
共有n个路口,n个路口间存在着m条道路,每条道路连接两个路口,道路有其各自的长度。
GrassLand和他的实验室在1号路口,而他的师弟在n号路口。
师弟沿着最短路径走向实验室,若有多于一条的最短路径,他会任意选择一条。
GrassLand不希望走的太远而浪费科研的时间,所以他至多只会离开实验室k个路口。
问题出现了,GrassLand并不知道他的师弟会选择哪条路径。所以他想知道,所有离开实验室不超过k个路口(即该路口和实验室可以由至多k条道路连接)的路口中,在师弟和实验室间任意一条最短路径上的路口个数(包括实验室所在的1号路口和师弟所在的n号路口)。

输入:

输入包含多组测试用例。
每组测试用例开头为三个整数n(2 <= n <= 1000),m(1 <= m <= 100000),k(0 <= k <= 1000)
接下去m行描述道路信息,每行三个整数a(1 <= a <= n),b(1 <= b <= n && b != a),c(1 <= c <= 1000),表示连接路口a和路口b的道路长度为c。
数据保证1号路口和n号路口间连通。

输出:

对于每组测试用例,输出一个整数,代表符合条件的路口个数。

样例输入:
4 3 2
1 2 1
2 3 1
3 4 1
4 3 1
1 2 1
2 3 1
3 4 1
4 4 1
1 2 3
1 3 2
2 4 2
3 4 3
样例输出:
3
2
3