记录编号	578494	评测结果	AAAAAAAAAA
题目名称	[NOIP 2017]逛公园	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	2.626 s
提交时间	2023-03-22 07:55:49	内存使用	65.52 MiB

#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second
#define Chtholly std::set<node>::iterator
using i64 = long long;
using u64 = unsigned long long;
using pii = std::pair<int,int>;
using pli = std::pair<i64,int>;

const int maxn = 1e5 + 5;
const int maxm = 55;
int n,m,k;
i64 mod;
void add(i64& x,i64 y) {x += y;if(x >= mod)x -= mod;return ;}
void sub(i64& x,i64 y) {x -= y;if(x < 0)x += mod;return ;}
i64 inc(i64 x,i64 y) {return (x + y) >= mod ? (x + y - mod) : (x + y);}
i64 dec(i64 x,i64 y) {return (x - y) < 0 ? (x - y + mod) : (x - y);}
i64 power(i64 x,i64 y) {i64 ans = 1;for(;y;y >>= 1) {if(y & 1)(ans *= x) %= mod;(x *= x) %= mod;}return ans;}
std::vector<pii> G[maxn],S[maxn];
std::vector<int> Z[maxn],scc[maxn];
i64 dis[maxn],dist[maxn];
bool vis[maxn],ins[maxn],tra[maxn][maxm];
int stk[maxn],tp,dfn[maxn],low[maxn],tot,num,bel[maxn];

void tarjan(int u) {
	stk[++ tp] = u;
	ins[u] = true;
	dfn[u] = low[u] = ++ num;
	for(auto& v : Z[u]) {
		if(!dfn[v])
			tarjan(v),low[u] = std::min(low[u] , low[v]);
		else if(ins[v])
			low[u] = std::min(low[u] , dfn[v]);
	}
	if(dfn[u] == low[u]) {
		++ tot;
		do {
			scc[tot].pb(u);
			bel[u] = tot;
			ins[u] = false;
		} while(stk[tp --] != u);
	}
	return ;
}

i64 f[maxn][maxm];

i64 dp(int x,int y) {
	if(x == 1&&y == 0)
		return 1;
	if(tra[x][y])
		return f[x][y];
	tra[x][y] = true;
	i64& val = f[x][y];
	for(pii& p : S[x]) {
		int v = p.fir,w = p.sec;
		if(dis[x] - dis[v] + y - w >= 0&&dis[x] - dis[v] + y - w <= k)
			add(val , dp(v , dis[x] - dis[v] + y - w));
	}
	return val;
}

void work() {
	scanf("%d %d %d %lld",&n,&m,&k,&mod);
	for(int i = 1;i <= tot;++ i)
		scc[i].clear();
	tot = tp = num = 0;
	for(int i = 1;i <= n;++ i)
		G[i].clear(),S[i].clear(),Z[i].clear();
	memset(dfn , 0 , sizeof(dfn));
	memset(low , 0 , sizeof(low));
	memset(bel , 0 , sizeof(bel));
	for(int i = 1;i <= m;++ i) {
		int u,v,t;
		scanf("%d %d %d",&u,&v,&t);
		G[u].pb(v , t);
		S[v].pb(u , t);
		if(!t)
			Z[u].pb(v);
	}
	memset(vis , false , sizeof(vis));
	memset(dis , 0x3f , sizeof(dis));
	std::priority_queue<pli,std::vector<pli>,std::greater<pli> > q;
	q.emplace(dis[1] = 0 , 1);
	while(!q.empty()) {
		int u = q.top().sec;
		q.pop();
		if(vis[u])
			continue ;
		vis[u] = true;
		for(pii& p : G[u]) {
			int v = p.fir,w = p.sec;
			if(dis[v] > dis[u] + w)
				q.emplace(dis[v] = dis[u] + w , v);
		}
	}
	memset(vis , false , sizeof(vis));
	memset(dist , 0x3f , sizeof(dist));
	q.emplace(dist[n] = 0 , n);
	while(!q.empty()) {
		int u = q.top().sec; 
		q.pop();
		if(vis[u])
			continue ;
		vis[u] = true;
		for(pii& p : S[u]) {
			int v = p.fir,w = p.sec;
			if(dist[v] > dist[u] + w)
				q.emplace(dist[v] = dist[u] + w , v);
		}
	}
	for(int i = 1;i <= n;++ i)
		if(!dfn[i])
			tarjan(i);
	for(int i = 1;i <= tot;++ i) {
		if(scc[i].size() <= 1)
			continue ;
		for(auto& v : scc[i])
			if(dis[v] + dist[v] <= dis[n] + k)
				return puts("-1"),void();
	}
	memset(f , 0 , sizeof(f));
	memset(tra , false , sizeof(tra));
	i64 ans = 0;
	for(int i = 0;i <= k;++ i)
		add(ans , dp(n , i));
	printf("%lld\n",ans);
	return ;
}

int main() {
	freopen("2017park.in","r",stdin);
	freopen("2017park.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T --)
		work();
	return 0;
}