题意分析
记忆化搜索
需要最短路，先可以通过 Dijkstra $\mathcal O\left((n+m)\log m\right)$ 求出 $1\sim i$ 的最短路长度 $dis_i$。
分析题目条件，“方案数无穷多”，即存在 $0$ 环，如何判断 $0$ 环下文会讲。
合法路线显然非常大，因此暴力枚举是行不通的，考虑 DP 递推求解。
设 $dp_{u,k}$ 表示 $1\sim u$ 的长度为 $dis_u+k$ 的路径数，这样答案即 $\sum\limits_{i=0}^Kdp_{n,i}$。
那么如何递推呢？
设 $V$ 为可以到达节点 $u$ 的节点 $v$ 的集合，$w_{u,v}$ 表示边 $(v,u)$ 的边权。
则有：
\[\large dp_{u,k}=\sum_{v\in V}dp_{v,dis_{u}+k-dis_{v}-w_{u,v}}\]即：$1\sim v$ 的路径长度恰好为 $dis_{v}+(dis_u+k-dis_v-w_{u,v})=dis_u+k-w_{u,v}$，即减去边权。
同时，对于 $dp_{u,k}$，如果 $k$ 不满足 $0\leq k\leq K$，则没有意义，答案为 $0$。
特别地，$dp_{1,0}=1$。
那么，写一个记忆化搜索 DP 求解即可。
$0$ 环
说了这么多，如何判断 $0$ 环呢？
既然是环，那么 DFS 过程中一定会在某一时刻，访问到之前访问过的节点。
放到 Tarjan 里就是出现回溯边，但是这里用不着那么麻烦。
DFS 有两个参数 $u,k$，我们可以记 $vis_{u,k}$ 表示状态 $[u,k]$ 是否在递归栈中。
如果在修改 $vis_{u,k}$ 之前就发现 $vis_{u,k}$ 有值，即代表出现了一个环，且是 $0$ 环。
这个时候，需要立刻退出 DFS，否则会出现类似于“无限递归”的情况，然后 $\text{TLE}$。
AC 代码
时间复杂度：$\mathcal O\left((n+m)\log m+nk\right)$。
前一部分是 Dijkstra，后一部分是记搜（状态量 $\mathcal O(nk)$，转移 $\mathcal O(1)$）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=1e5,M=2e5,Kmax=50;
struct graph{
struct edge{
int v,r,w;
}a[M+1];
int size,h[N+1];
void clear(){
size=0;
memset(h,0,sizeof(h));
}
void create(int u,int v,int w){
a[++size]={v,h[u],w};
h[u]=size;
}
}g,rg;
int n,m,K,P;
int dis[N+1];
int Dijkstra(int s,int t){
memset(dis,0x3f,sizeof(dis));
static bool vis[N+1];
memset(vis,0,sizeof(vis));
dis[s]=0;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
q.push({dis[s],s});
while(q.size()){
int x=q.top().second;q.pop();
if(vis[x]){
continue;
}
vis[x]=true;
for(int i=g.h[x];i;i=g.a[i].r){
int &v=g.a[i].v;
if(vis[v]){
continue;
}
if(dis[x]+g.a[i].w<dis[v]){
dis[v]=dis[x]+g.a[i].w;
q.push({dis[v],v});
}
}
}
return dis[t];
}
bool vis[N+1][Kmax+1];
int dp[N+1][Kmax+1];
bool ring0;
int f(int u,int k){
if(ring0){
return -1;
}
if(k<0||K<k){
return 0;
}
if(vis[u][k]){
ring0=true;
return -1;
}
vis[u][k]=true;
if(dp[u][k]){
vis[u][k]=false;
return dp[u][k];
}
for(int i=rg.h[u];i;i=rg.a[i].r){
int &v=rg.a[i].v,&w=rg.a[i].w;
dp[u][k]=(1ll*dp[u][k]+f(v,dis[u]+k-dis[v]-w))%P;
}
if(u==1&&k==0){
vis[u][k]=false;
return 1;
}
vis[u][k]=false;
return dp[u][k];
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--){
g.clear();
rg.clear();
memset(dp,0,sizeof(dp));
memset(vis,0,sizeof(vis));
cin>>n>>m>>K>>P;
while(m--){
int u,v,w;
cin>>u>>v>>w;
g.create(u,v,w);
rg.create(v,u,w);
}
Dijkstra(1,n);
ring0=false;
f(n,K);
if(ring0){
cout<<"-1\n";
}else{
int ans=0;
for(int i=0;i<=K;i++){
ans=(1ll*ans+f(n,i))%P;
}
cout<<ans<<'\n';
}
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
