问题 3885 --逛公园

3885: 逛公园

题目描述

    策策同学特别喜欢逛公园。公园可以看成一张N个点M条边构成的有向图,且没有自环和重边。其中1号点是公园的入口,N号点是公园的出口,每条边有一个非负权值,代表策策经过这条边所要花的时间。
 策策每天都会去逛公园,他总是从1号点进去,从N号点出来。
 策策喜欢新鲜的事物,他不希望有两天逛公园的路线完全一样,同时策策还是一个特别热爱学习的好孩子,他不希望每天在逛公园这件事上花费太多的时间。如果1号点到N号点的最短路长为d,那么策策只会喜欢长度不超过d+K的路线。
策策同学想知道总共有多少条满足条件的路线,你能帮帮他吗?
为避免输出过大,答案对

输入

 第一行包含一个整数 T, 代表数据组数。
接下来

输出

输出文件包含T 行,每行一个整数代表答案。

样例输入输出

输入#1 复制
2
5 7 2 10
1 2 1
2 4 0
4 5 2
2 3 2
3 4 1
3 5 2
1 5 3
2 2 0 10
1 2 0
2 1 0
输出#1 复制
3
-1

提示

对于第一组数据,最短路为 3。
1 – 5, 1 – 2 – 4 – 5, 1 – 2 – 3 – 5 为 3条合法路径。

【测试数据与约定】
对于不同的测试点,我们约定各种参数的规模不会超过如下
  测试点编号  T N M k 是否有0 边
1  5  5  10  0  否
2  5  1000  2000  0  否
3  5  1000  2000  50  否
4  5  1000  2000  50  否
5  5  1000  2000  50  否
6  5  1000  2000  50  是
7  5  100000  200000  0  否
8  3  100000  200000  50  否
9  3  100000  200000  50  是
10  3  100000  200000  50  是
对于 100%的数据,  1 ≤ P ≤ 109,1 ≤ai , bi ≤ N, 0 ≤ ci ≤  1000。
数据保证:至少存在一条合法的路线。

序号 标题 作者 发表时间 费用 订购数 操作