大致思路 缩点 然后环内看看是不是每条路都是0 如果是说明这个环是0环 跑记搜的时候判断是否经过0环的点且对它有贡献 如果有说明有无穷个解 输出-1 然后WA了 原因就是少判断了-1的解

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#include <stack>

#define N (int)(1e5+5)
#define M (int)(2e5+5)

using namespace std;

bool vis[N],flag[N],is_zero[N],used[N];
int dfn[N],low[N],dis[N],id[N],head[N],tp[N],dp[N][60],is_dp[N][60],cnt,tot,color_tot;
int t,n,m,k,FL,mod;

struct edge {
	int nex,to,w;
}e[M];

void add(int x,int y,int z) {
	e[++cnt]=edge{head[x],y,z};
	head[x]=cnt;
}

int rd() {
	int f=1,sum=0; char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return sum*f;
}

void spfa() {
	queue<int>q;
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	q.push(1); dis[1]=0; 
	while(!q.empty()) {
		int x=q.front(); q.pop();
		vis[x]=0;
		for(int i=head[x];i;i=e[i].nex) {
			int y=e[i].to;
			if(dis[y]>dis[x]+e[i].w) {
				dis[y]=dis[x]+e[i].w;
				if(!vis[y]) {
					vis[y]=1;
					q.push(y);
				}
			}
		}
	}
}

stack<int>s;
void tarjan(int x) {
	dfn[x]=low[x]=++tot;
	flag[x]=1;
	s.push(x);
	for(int i=head[x];i;i=e[i].nex) {
		int y=e[i].to;
		if(!dfn[y]) {
			tarjan(y);
			low[x]=min(low[x],low[y]);
		} else if(flag[y]) {
			low[x]=min(low[x],dfn[y]);
		}
	}
	if(low[x]==dfn[x]) {
		int qwq;
		++color_tot;
		do {
			qwq=s.top(); s.pop();
			id[qwq]=color_tot; flag[qwq]=0;
		}while(qwq!=x);
		tp[color_tot]=x;
	}
}

void bfs(int x,int color) {
	queue<int>q;
	q.push(x); used[x]=1; int ok=1,tot=0;
	while(!q.empty()) {
		int x=q.front(); q.pop();
		++tot;
		for(int i=head[x];i;i=e[i].nex) {
			int y=e[i].to;
			if(id[y]!=color||used[y]) continue;
			if(e[i].w!=0) {
				ok=2;
				return;	
			}
			q.push(y);
			used[y]=1;
		}
	}
	if(ok!=2&&tot>1) is_zero[color]=1;
}

void work() {
	memset(used,0,sizeof(used));
	for(int i=1;i<=color_tot;i++) {
		bfs(tp[i],i);
	//	cout<<i<<":"<<is_zero[i]<<endl;
	}
}

int dfs(int x,int w) {
	if(w>k) return 0;
	if(is_dp[x][w]) return dp[x][w];
	dp[x][w]=0; is_dp[x][w]=1;
	if(x==n) ++dp[x][w];
	for(int i=head[x];i;i=e[i].nex) {
		int y=e[i].to;
		int qwq=dfs(y,w+dis[x]+e[i].w-dis[y]);
		if(qwq&&is_zero[id[y]]) {
			FL=1;
			return 0;
		}
		dp[x][w]+=qwq;
		dp[x][w]%=mod;
	}
	dp[x][w]%=mod;
	return dp[x][w];
} 

void solve() {
	memset(head,0,sizeof(head));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(id,0,sizeof(id));
	memset(flag,0,sizeof(flag));
	memset(is_zero,0,sizeof(is_zero));
	memset(dp,0,sizeof(dp));
	memset(is_dp,0,sizeof(is_dp));
	memset(e,0,sizeof(e));
	memset(tp,0,sizeof(tp));
	cnt=tot=color_tot=FL=0;
	n=rd(); m=rd(); k=rd(); mod=rd();
	int x,y,z;
	for(int i=1;i<=m;i++) {
		x=rd(); y=rd(); z=rd();
		add(x,y,z);
	}
	spfa();
	for(int i=1;i<=n;i++)
		if(!dfn[i]) {
			while(!s.empty()) s.pop();
			tarjan(i);
		}
	work();
	int ans=dfs(1,0);
	if(FL) printf("-1\n");
	else printf("%d\n",((ans%mod)+mod)%mod);
}

int main() {
	t=rd();
	while(t--) {
		solve();
	}
}