麻烦看看。TLE

#include<bits/stdc++.h>
using namespace std;
#define re register
#define int long long
const int sz=1e5+5;
inline int read()
{
	char ch;
	int r=0,f=1;
	ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') f=-1,ch=getchar();
	while(ch>='0'&&ch<='9') r=r*10+ch-'0',ch=getchar();
	return r*f;
}
int n,m,k,p,T;
bool vis[sz];
struct node
{
  int to,nxt,w;	
}e[sz];
int head[sz],cnt,dis[sz],f[sz][105],D,sum[sz];
void add_edge(int x,int y,int w)
{
 e[++cnt].to=y;
 e[cnt].nxt=head[x];
 e[cnt].w=w;
 head[x]=cnt;	
}
struct node1
{
 int id,d;	
};
void spfa(int s)
{
 queue<node1> q;
 memset(vis,0,sizeof(vis));
 memset(dis,0x3f3f,sizeof(dis));
 memset(sum,0,sizeof(sum));
 dis[s]=0,vis[s]=1,sum[s]=1;
 q.push((node1){s,0});
 while(!q.empty())
 {
  node1 top=q.front();q.pop();
  int id=top.id,d=top.d;
  vis[id]=0;
  for(re int i=head[id];i;i=e[i].nxt)
   if(dis[e[i].to]>=e[i].w+dis[id])
    {
	 dis[e[i].to]=e[i].w+dis[id],sum[e[i].to]=sum[id]+1; 	
     if(sum[e[i].to]>=n) 
      {
      	cout<<-1<<endl;
      	exit(0);
	  }
	 if(!vis[e[i].to]) q.push((node1){e[i].to,dis[e[i].to]}),vis[e[i].to]=1;  
	}	
 }      	
} 
inline int dfs(int now,int l,int lim)
{ 
 int s=0;
 if(l<0||l>lim) return 0;
 if(l==lim&&now==1) 	
 return f[now][lim-l]=1;
 for(re int i=head[now];i;i=e[i].nxt)
 { 
//  cout<<lim<<" "<<l<<" "<<e[i].w<<endl;	
  if(lim>=l+e[i].w)	
   if(f[e[i].to][lim-l-e[i].w]) 
	 s=(f[e[i].to][lim-l-e[i].w]+s)%p;
  else 
  s=(s+dfs(e[i].to,l+e[i].w,lim))%p;  	
 } 
 return f[now][lim-l]=s;
}  
signed main()
{ 
//  freopen("12.out","w",stdout);
  T=read(); 
  while(T--) 
  { 
   memset(e,0,sizeof(e));
   memset(head,0,sizeof(head));
   int ans=0;
   n=read(),m=read(),k=read(),p=read();
   for(re int i=1;i<=m;i++)
   { 
    int u=read(),v=read(),w=read();
	add_edge(v,u,w);	
   } 
   spfa(n);
   D=dis[1];
   for(re int i=0;i<=k;i++)
   {
    memset(f,0,sizeof(f));
    ans=(ans+dfs(n,0,D+i))%p;	
   }
   printf("%lld\n",ans);
  } 
} 
/*
2
5 7 2 10
1 2 1
2 4 0
4 5 2
2 3 2
3 4 1
3 5 2
1 5 3
2 2 0 10
1 2 0
2 1 0
*/