WA#7,8,9,10。输出比答案小。

思路就是先 tarjan 找0环然后判-1，判-1这段代码没问题。然后再记忆化搜索算方案，但是输出比答案小多了！改了几小时了，求条！！感激不尽！

#include<bits/stdc++.h>
using namespace std;
using pi=pair<int,int>;
const int N=1e5+5;
int T,n,m,K,mod,tot,dfn[N],low[N],vis[N],stk[N],top,cor[N],cr,f[N],g[N],d[N][51],vas[N][51];
struct no{
	int v,l,id;
};
vector<no>w[N],e[N];
vector<pi>E[N];
void Clear(){
	tot=top=cr=0;
	for(int i=1;i<=n;i++){
		e[i].clear();
		E[i].clear();
		w[i].clear();
		g[i]=f[i]=1e9;
		dfn[i]=low[i]=vis[i]=cor[i]=0;
		for(int j=0;j<=K;j++)d[i][j]=vas[i][j]=0;
	}
}
void tarjan(int u){
	dfn[u]=low[u]=++tot;
	vis[u]=1;
	stk[++top]=u; 
	for(no vt:w[u]){
		int v=vt.v;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(vis[v])low[u]=min(low[u],low[v]);
	}
	if(low[u]==dfn[u]){
		cr++;
		while(stk[top]!=u){
			cor[stk[top]]=cr;
			vis[stk[top--]]=0;
		}
		cor[stk[top]]=cr;
		vis[stk[top--]]=0;
	}
}
void dij0(){
	priority_queue<pi,vector<pi>,greater<pi>>q;
	f[1]=0;
	q.push({0,1});
	while(!q.empty()){
		auto up=q.top();
		q.pop();
		int u=up.second,l=up.first;
		if(f[u]<l)continue;
		for(no vt:e[u]){
			int v=vt.v,r=vt.l;
			if(f[u]+r<f[v]){
				f[v]=f[u]+r;
				q.push({f[v],v});
			}
		}
	}
	g[n]=0;
	q.push({0,n});
	while(!q.empty()){
		auto up=q.top();
		q.pop();
		int u=up.second,l=up.first;
		if(g[u]<l)continue;
		for(pi vt:E[u]){
			int v=vt.first,r=vt.second;
			if(g[u]+r<g[v]){
				g[v]=g[u]+r;
				q.push({g[v],v});
			}
		}
	}
}
int dfs(int u,int x){
	if(vas[u][x])return d[u][x];
	vas[u][x]=1;
	for(pi vt:E[u]){
		int v=vt.first,l=vt.second,y=f[u]+x-l-f[v];
		if(0<=y&&y<=K)(d[u][x]+=dfs(v,y))%=mod;
	}
	return d[u][x];
}
void slove(){
	cin>>n>>m>>K>>mod;
	Clear();
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		e[x].push_back({y,z,i});
		E[y].push_back({x,z});
		if(!z)w[x].push_back({y,z,i});
	}
	dij0();
	for(int i=1;i<=n;i++)
		if(!dfn[i])tarjan(i);
	for(int i=1;i<=n;i++)
		for(no j:w[i])
			if(cor[i]==cor[j.v]){
				if(f[i]!=1e9&&g[j.v]!=1e9&&f[i]+g[j.v]<=g[1]+K){
					cout<<-1<<"\n";
					return;
				}
				vis[j.id]=1;
			}
	for(int i=1;i<=n;i++)E[i].clear();
	for(int i=1;i<=n;i++)
		for(no j:e[i])
			if(!vis[j.id])E[j.v].push_back({i,j.l});
	d[1][0]=1%mod;
	vas[1][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=K;j++)d[i][j]=dfs(i,j);
	int ans=0;
	for(int i=0;i<=K;i++)(ans+=d[n][i])%=mod;
	cout<<ans<<"\n";
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--)slove();
	return 0;
}