题意：
策策同学特别喜欢逛公园。 公园可以看成一张 N 个点 M 条边构成的有向图，且没有自环和重边。其中 1 号点是公园的入口， N 号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。
策策每天都会去逛公园，他总是从 1 号点进去，从 N 号点出来。
策策喜欢新鲜的事物，他不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，他不希望每天在逛公园这件事上花费太多的时间。如果 1 号点到 N 号点的最短路长为 d，那么策策只会喜欢长度不超过 d+K 的路线。
策策同学想知道总共有多少条满足条件的路线，你能帮帮他吗？
为避免输出过大，答案对 P 取模。
如果有无穷多条合法的路线，请输出 −1 。
n<=1e5，m<=2e5，K<=50,1≤P≤1e9，0≤ci≤1000。
思路：因为K很小，建立以1为源点的最短路图，在最短路图上进行DP计数
dp[i][j]表示当前在点i，比最短路线多走j时间的方案数
在1到N的最短路上可能有环，这样会出现-1的情况，同时还有边长为0的存在，这两个问题都可以使用拓扑排序解决
对于-1拓扑排序后直接判断
对于边长为0按照拓扑序进行转移
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef vector<int> VI;
#define fi first
#define se second
#define MP make_pair
#define N 110000
#define M 210000
#define eps 1e-8
#define pi acos(-1)
priority_queue<pair<int,int> > q; int dp[N][],head[M],vet[M],nxt[M],len[M],head2[M],vet2[M],nxt2[M],len2[M],
dis[N],dis2[N],vis[N],p[N],d[N],tot,tot2; void add(int a,int b,int c)
{
nxt[++tot]=head[a];
vet[tot]=b;
len[tot]=c;
head[a]=tot;
} void add2(int a,int b,int c)
{
nxt2[++tot2]=head2[a];
vet2[tot2]=b;
len2[tot2]=c;
head2[a]=tot2;
} int main()
{
//freopen("uoj331.in","r",stdin);
// freopen("uoj331.out","w",stdout);
int cas;
scanf("%d",&cas);
for(int v1=;v1<=cas;v1++)
{
int n,m,K,MOD;
scanf("%d%d%d%d",&n,&m,&K,&MOD);
tot=tot2=;
memset(head,,sizeof(head));
memset(head2,,sizeof(head2));
for(int i=;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add2(y,x,z);
}
//printf("readend\n");
memset(vis,,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
memset(d,,sizeof(d));
q.push(MP(,)); dis[]=;
while(!q.empty())
{
int u=q.top().se;
q.pop();
if(vis[u]) continue;
vis[u]=;
int e=head[u];
while(e)
{
int v=vet[e];
if(dis[u]+len[e]<dis[v])
{
dis[v]=dis[u]+len[e];
q.push(MP(-dis[v],v));
}
e=nxt[e];
}
}
//printf("dijk1end\n");
memset(vis,,sizeof(vis));
memset(dis2,0x3f,sizeof(dis2));
q.push(MP(,n)); dis2[n]=;
while(!q.empty())
{
int u=q.top().se;
q.pop();
if(vis[u]) continue;
vis[u]=;
int e=head2[u];
while(e)
{
int v=vet2[e];
if(dis2[u]+len2[e]<dis2[v])
{
dis2[v]=dis2[u]+len2[e];
q.push(MP(-dis2[v],v));
}
e=nxt2[e];
}
}
//printf("dijk2end\n");
for(int i=;i<=n;i++)
{
int e=head[i];
while(e)
{
int v=vet[e];
if(dis[i]+len[e]==dis[v]) d[v]++;
e=nxt[e];
}
}
tot=;
for(int i=;i<=n;i++)
if(!d[i]) p[++tot]=i;
//printf("%d\n",tot);
for(int i=;i<=tot;i++)
{
int u=p[i];
int e=head[u];
while(e)
{
int v=vet[e];
if(dis[u]+len[e]==dis[v])
{
d[v]--;
if(!d[v]) p[++tot]=v;
}
e=nxt[e];
}
}
//printf("topoend\n");
int flag=;
for(int i=;i<=n;i++)
if(d[i]&&dis[i]+dis2[i]<=dis[n]+K)
{
printf("-1\n");
flag=;
break;
}
if(!flag) continue;
memset(dp,,sizeof(dp));
dp[][]=;
for(int k=;k<=K;k++)
{
for(int i=;i<=tot;i++)
{
int u=p[i];
int e=head[u];
while(e)
{
int v=vet[e];
if(dis[u]+len[e]==dis[v]) dp[v][k]=(dp[v][k]+dp[u][k])%MOD;
e=nxt[e];
}
} for(int i=;i<=n;i++)
{
int e=head[i];
while(e)
{
int v=vet[e];
int t=k+dis[i]+len[e]-dis[v];
if(dis[i]+len[e]!=dis[v]&&t<=K) dp[v][t]=(dp[v][t]+dp[i][k])%MOD;
e=nxt[e];
}
}
}
ll ans=;
for(int i=;i<=K;i++) ans=(ans+dp[n][i])%MOD;
printf("%lld\n",ans);
}
return ;
}