首先需要一个 Dijkstra 求最短路。设 (d_u) 表示从 (1) 到 (u) 的最短路。
设 (g_{u,j}) 表示从 (1) 点到 (u) 点，长度恰好等于 (j) 的路径种数。那么可以列出式子
[g_{u,j}=
egin{cases}
1(u=1,j=0)\
sum g_{v,j-c(v,u)}(otherwise)
end{cases}
]
。然后我们就可以 DP 了。
慢着……为什么这题可以 DP 呢？
DP 的一个必要条件是，不存在一个状态使得它向自己转移。假设本题中的某个状态能向自己转移，那么很明显原图中存在一个边权全为 (0) 的环。因此，判掉 (0) 环后，本题的状态转移就没有环了（实际上，一切 DP 的过程都可以看作一个以状态为点，以转移为边的有向图，且它一定是一个拓扑图）。
现在有一个严重的问题：这个 DP 有 (Ncdot max d_i) 种状态，好像只能拿 (10) 分。
我们发现， (K) 不是很大，想到设 (f_{u,j}) 表示从 (1) 点到 (u) 点，长度恰好等于 (d_u+j) 的路径种数。方程
[f_{u,j}=
egin{cases}
1(u=1,j=0)\
sum f_{v,d_u+j-c(v,u)-d_v}(otherwise)
end{cases}
]
。答案就是(sum_{j=0}^K f_{n,j})。
显然，状态一共只有 (O(NK)) 种。转移顺序不明显，可以用记忆化搜索实现；关于 (0) 环，只要在记忆化搜索的过程中顺便判判就好了。总时间复杂度(O(Mlog M+MK))，可以通过本题。
#include<cstdio>
#include<queue>
#include<cstring>
inline int read(){
int a=0;char c=getchar();
for(;c<48||c>57;c=getchar());for(;c>47&&c<58;a=a*10+c-48,c=getchar());
return a;
}
using namespace std;
const int N=1e5+1,K=51;
struct edge{int v,c,nxt;}g[400001];
int n,m,l,M,s,f[N][K],used[N][K],d[N],head[N+N],k;
inline int Push(int u,int v,int c){g[++k]=(edge){v,c,head[u]};head[u]=k;}
typedef pair<int,int>P;priority_queue<P,vector<P>,greater<P> >p;
inline int Sp(){
int u,v;
memset(d,127,sizeof d);
p.push(P(d[1]=0,1));
for(;!p.empty();){
u=p.top().second;
if(p.top().first>d[u]){p.pop();continue;}
p.pop();
for(int i=head[u];i;i=g[i].nxt)if(g[i].c+d[u]<d[v=g[i].v])
d[v]=d[u]+g[i].c,p.push(P(d[v],v));
}
}
inline int Mod(int a){return a>=M?a-M:a;}
int dfs(int u,int k){
if(used[u][k])return-1;
if(f[u][k]<M)return f[u][k];
f[u][k]=u==1&&!k?1:0;
used[u][k]=1;
int v,t;
for(int i=head[u+n];i;i=g[i].nxt){v=g[i].v;
t=k-d[v]-g[i].c+d[u];
if(t>=0&&t<=l)
if(~dfs(v,t))f[u][k]=Mod(f[v][t]+f[u][k]);
else return f[u][k]=-1;
}used[u][k]=0;
return f[u][k];
}
int main()
{
int u,v,c,fl;
int T=read();for(;T--;){
k=0;memset(head,0,sizeof head);
n=read();m=read();l=read();M=read();
for(;m--;)u=read(),v=read(),c=read(),Push(u,v,c),Push(v+n,u,c);
Sp();
for(int i=1;i<=n;i++)
for(int j=0;j<=l;j++)
f[i][j]=M;
s=0;fl=1;memset(used,0,sizeof used);
for(int j=0;j<=l;j++)
if(dfs(n,j)<0){fl=0;break;}
else s=Mod(s+f[n][j]);
printf("%d
",fl?s:-1);
}return 0;
}