题目描述
策策同学特别喜欢逛公园。公园可以看成一张NNN个点MMM条边构成的有向图，且没有 自环和重边。其中1号点是公园的入口，NNN号点是公园的出口，每条边有一个非负权值， 代表策策经过这条边所要花的时间。
策策每天都会去逛公园，他总是从1号点进去，从NNN号点出来。
策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一个 特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果1号点 到NNN号点的最短路长为ddd，那么策策只会喜欢长度不超过d+Kd + Kd+K的路线。
策策同学想知道总共有多少条满足条件的路线，你能帮帮它吗？
为避免输出过大，答案对PPP取模。
如果有无穷多条合法的路线，请输出?1。
输入输出格式
输入格式：第一行包含一个整数 TTT, 代表数据组数。
接下来TTT组数据，对于每组数据： 第一行包含四个整数 N,M,K,PN,M,K,PN,M,K,P，每两个整数之间用一个空格隔开。
接下来MMM行，每行三个整数ai,bi,cia_i,b_i,c_iai?,bi?,ci?，代表编号为ai,bia_i,b_iai?,bi?的点之间有一条权值为 cic_ici?的有向边，每两个整数之间用一个空格隔开。
输出格式：输出文件包含 TTT 行，每行一个整数代表答案。
输入输出样例
输入样例#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
说明
【样例解释1】
对于第一组数据，最短路为 3。 1 – 5, 1 – 2 – 4 – 5, 1 – 2 – 3 – 5 为 3 条合法路径。
【测试数据与约定】
对于不同的测试点，我们约定各种参数的规模不会超过如下
| 测试点编号 | TTT | NNN | MMM | KKK | 是否有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≤10001 \le P \le 10^9,1 \le a_i,b_i \le N ,0 \le c_i \le 10001≤P≤109,1≤ai?,bi?≤N,0≤ci?≤1000。
数据保证：至少存在一条合法的路线。
题解
考场上想到了dp，甚至写出了转移方程，但是由于时间紧迫没有进一步想得出转移顺序，最后交了最短路。。。QAQ
我们看K最大50，考虑一个关于K的dp
设f[u][j]表示到达u路径比到达u的最短路长j的方案数
那么对于一个f[u][j]，u的所有边u -> v，有转移方程f[v][d[u] + j + w - d[v]] += f[u][j]
因为当前从1到v的路经长L = 1到u的路经长d[u] + j 加上 边权w，减去d[v]就得到比最短路多的部分
只要这个值不大于K，都可以转移
考虑转移顺序。
由最短路我们有d[v] <= d[u] + w
也就是说d[u] + w - d[v] + j >= j
由于等号的存在我们会产生同状态的转移，这个时候就要考虑转移的顺序
有两种情况：
1、沿着最短路转移
2、沿着0边转移
我们只要确保这两种情况中最靠前的节点先转移就好了
1、对于最短路，最靠前就是d最小的，按d排个序就好了
2、而0边呢，最靠前先转移你想到了什么？
对，拓扑排序：
我们单独用0边建图，跑一次拓扑排序给每个0点标上拓扑序
这样子我们对所有的点双关键字排序，第一关键字最短路，第二关键字拓扑序，因为只有0边两端存在d相等的情况，所以其他的点拓扑序赋什么值都无所谓
最后我们按照排序的顺序写状态转移就A啦~
附上我丑丑的代码：
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define fo(i,x,y) for (int i = (x); i <= (y); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 200005,maxm = 400005,maxk = 60,INF = 1000000000;
inline int read(){int out = 0,flag = 1;char c = getchar();while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}return out * flag;
}
int N,M,K,P;
int dS[maxn],dT[maxn],f[maxn][maxk],inde[maxn],id[maxn];
bool vis[maxn],zer[maxn];
int head[maxn],nedge = 0,h[maxn],ne = 0;
struct EDGE{int to,w,next;}edge[maxm],e[maxm];
inline void build(int u,int v,int w){edge[nedge] = (EDGE) {v,w,head[u]}; head[u] = nedge++;e[ne] = (EDGE) {u,w,h[v]}; h[v] = ne++;if (!w) zer[u] = zer[v] = true,inde[v]++;
}
struct node{int u,d;};
inline bool operator <(const node& a,const node& b){return a.d > b.d;}
struct Node{int d,ti;}E[maxn];
inline bool cmp(const int& a,const int& b){return E[a].d == E[b].d ? E[a].ti < E[b].ti : E[a].d < E[b].d;}
void dijkstraS(){REP(i,N) dS[i] = INF,vis[i] = false;priority_queue<node> q;dS[1] = 0;q.push((node){1,dS[1]});node u; int to;while (!q.empty()){u = q.top();q.pop();if (vis[u.u]) continue;vis[u.u] = true;Redge(u.u)if (!vis[to = edge[k].to]){if (dS[to] >= dS[u.u] + edge[k].w){dS[to] = dS[u.u] + edge[k].w;q.push((node){to,dS[to]});}}}
}
void dijkstraT(){REP(i,N) dT[i] = INF,vis[i] = false;priority_queue<node> q;dT[N] = 0;q.push((node){N,dT[N]});node u; int to;while (!q.empty()){u = q.top();q.pop();if (vis[u.u]) continue;vis[u.u] = true;for (int k = h[u.u]; k != -1; k = e[k].next)if (!vis[to = e[k].to] && dT[to] > dT[u.u] + e[k].w){dT[to] = dT[u.u] + e[k].w;q.push((node){to,dT[to]});}}
}
bool tuopu(){queue<int> q;REP(i,N){id[i] = i;E[i].d = dS[i]; E[i].ti = 0;if (zer[i] && !inde[i]){q.push(i);}}int u,to,cnt = 0;while (!q.empty()){u = q.front();q.pop();E[u].ti = ++cnt;Redge(u) if (!edge[k].w){inde[to = edge[k].to]--;if (!inde[to]) q.push(to);}}REP(i,N) if (zer[i] && inde[i] && dS[i] + dT[i] <= dT[1] + K) {printf("-1\n");return false;}sort(id + 1,id + 1 + N,cmp);//REP(i,N) cout<<id[i]<<' ';cout<<endl;return true;
}
void solve(){dijkstraS();dijkstraT();//REP(i,N) cout<<f[i][0]<<' ';cout<<endl;if(!tuopu()) return;f[1][0] = 1;for (int j = 0; j <= K; j++)for (int i = 1; i <= N; i++){int u = id[i];Redge(u){int v = edge[k].to;if (dS[u] + j + edge[k].w - dS[v] <= K){f[v][dS[u] + j + edge[k].w - dS[v]] = (f[v][dS[u] + j + edge[k].w - dS[v]] + f[u][j]) % P;}}}int ans = 0;for (int i = 0; i <= K; i++) ans = (ans + f[N][i]) % P;printf("%d\n",ans);
}
void init(){int a,b,c;memset(f,0,sizeof(f));N = read(); M = read(); K = read(); P = read();ne = nedge = 0;REP(i,N) head[i] = h[i] = -1,inde[i] = 0,zer[i] = false;while (M--) {a = read(); b = read(); c = read(); build(a,b,c);}
}
int main()
{int T = read();while (T--){init();solve();}return 0;
}