记录编号	481744	评测结果	AAAAAAAAAA
题目名称	[NOIP 2017]逛公园	最终得分	100
用户昵称	HT008	是否通过	通过
代码语言	C++	运行时间	1.583 s
提交时间	2018-01-04 09:59:48	内存使用	72.61 MiB

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define ms(a,b,c) memset(a,b,sizeof(c))
#define il inline
using namespace std;
const int maxm=210000;
int dis[maxm],dp[maxm][60];
int head[maxm],net[maxm*2],to[maxm*2],cost[maxm*2];
int headx[maxm],netx[maxm*2],tox[maxm*2],costx[maxm*2];
int cnt,n,m,k,p;
bool vis[maxm],used[maxm][60];
queue <int> dl;
int flag=1; 
il void add(int x,int y,int z)
{
	to[++cnt]=y;
	cost[cnt]=z;
	net[cnt]=head[x];
	head[x]=cnt;
} 
il void addf(int x,int y,int z)
{
	tox[++cnt]=y;
	costx[cnt]=z;
	netx[cnt]=headx[x];
	headx[x]=cnt;
}
il void init()
{
	ms(dis,127/3,dis),ms(dp,-1,dp);
	ms(head,0,head),ms(net,0,net),ms(to,0,to),ms(cost,0,cost);
	ms(headx,0,headx),ms(netx,0,netx),ms(tox,0,tox),ms(costx,0,costx);
	ms(vis,0,vis),ms(used,0,used);
	cnt=0;
}
il void spfa()
{
	while(!dl.empty()) dl.pop();
	dl.push(1);
	vis[1]=1,dis[1]=0;
	while(!dl.empty())
	{
		int x=dl.front();
		dl.pop();
		vis[x]=0;
		
		for(int i=headx[x];i;i=netx[i])
		if(dis[tox[i]]>dis[x]+costx[i])
		{
			dis[tox[i]]=dis[x]+costx[i];
			if(!vis[tox[i]]) vis[tox[i]]=1,dl.push(tox[i]);
			//if(dis[n]==0) printf("--%d--\n",x);
		}
	}
}
il int read()
{
	int x=0,w=1;
	char ch=0;
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	 x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*w;
}
int dfs(int x,int rest)
{
	if(!flag) return 0;
	if(~dp[x][rest]) return dp[x][rest];
	used[x][rest]=1;
	dp[x][rest]=0;
	for(int i=head[x];i;i=net[i])
	{
		int tmp=to[i];
		int nowrest=dis[x]-dis[tmp]+rest-cost[i];
		if(nowrest<0) continue;
		if(used[tmp][nowrest]) 
		{
		   flag=0;	
		   return 0;
		}
		dp[x][rest]=(dp[x][rest]+dfs(tmp,nowrest))%p;
	}
	used[x][rest]=0;
	return dp[x][rest];
}
int main()
{
	freopen("2017park.in","r",stdin);
	freopen("2017park.out","w",stdout);
	int t;
	t=read();
	while(t--)
	{
		init();
		n=read(),m=read(),k=read(),p=read();
		for(int i=1;i<=m;i++)
		{
			int u,v,c;
			u=read(),v=read(),c=read();
			add(v,u,c),addf(u,v,c);
		}
		spfa();
		dp[1][0]=1;
		flag=1;
		int ans=0;
	    for(int i=0;i<=k&&flag;i++) ans=(ans+dfs(n,i))%p;
	    //dfs(n,k+1);
		if(!flag) ans=-1;
		printf("%d\n",ans); 
	}
	return 0;
}