rt

//P3953
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int dis[N], vis[N], dp[N][55], ins[N][55];
vector<pair<int, int> > g1[N], g2[N];
int t, n, m, k, p, ans, flg;

void spfa(){
	queue<int> q;
	dis[1] = 0, vis[1] = 1, q.push(1);
	while(!q.empty()){
		int x = q.front(); q.pop(); vis[x] = 0;
		for(int i = 0; i < g1[x].size(); ++ i){
			int y = g1[x][i].first, z = g1[x][i].second;
			if(dis[y] > dis[x] + z){
				dis[y] = dis[x] + z;
				if(!vis[y]) vis[y] = 1, q.push(y);
			}
		}
	}
}

int dfs(int x, int nowk){
	if(nowk < 0) return 0;
	if(ins[x][nowk] || flg){ flg = 1; return 0; }
	if(dp[x][nowk]) return dp[x][nowk];
	ins[x][nowk] = 1;
	for(int i = 0; i < g2[x].size(); ++ i){
		int y = g2[x][i].first, z = g2[x][i].second;
		dp[x][nowk] = (dp[x][nowk] + dfs(y, dis[x] - dis[y] - z + nowk)) % p;
		if(flg) return 0;
	}
	ins[x][nowk] = 0;
	return dp[x][nowk];
}

int main(){
	scanf("%d", &t);
	while(t--){
		ans = 0, flg = 0;
		memset(dp, 0, sizeof(dp));
		memset(vis, 0, sizeof(vis));
		memset(ins, 0, sizeof(ins));
		memset(dis, 127, sizeof(dis));
		for(int i = 0; i <= n; ++ i) g1[i].clear(), g2[i].clear();
		scanf("%d%d%d%d", &n, &m, &k, &p);
		for(int i = 1, a, b, c; i <= m; ++ i){
			scanf("%d%d%d", &a, &b, &c);
			g1[a].push_back(make_pair(b, c));
			g2[b].push_back(make_pair(a, c));
		}
		spfa();
		dp[1][0] = 1;
		for(int i = 0; i <= k; ++ i) ans = (ans + dfs(n, i)) % p;
		printf("%d\n", flg ? -1 : ans);
	}
	return 0;
}

原因：dp[1][0] = 1;

是否应该加强数据？