题目描述：
策策同学特别喜欢逛公园。公园可以看成一张 \(N\) 个点 \(M\) 条边构成的有向图，且没有 自环和重边。其中 \(1\) 号点是公园的入口，\(N\) 号点是公园的出口，每条边有一个非负权值， 代表策策经过这条边所要花的时间。
策策每天都会去逛公园，他总是从 \(1\) 号点进去，从 \(N\) 号点出来。
策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一个 特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果 \(1\) 号点 到 \(N\) 号点的最短路长为 \(d\)，那么策策只会喜欢长度不超过 \(d + K\) 的路线。
策策同学想知道总共有多少条满足条件的路线，你能帮帮它吗？
为避免输出过大，答案对 \(P\) 取模。
如果有无穷多条合法的路线，请输出 \(-1\)。
对于 \(100\%\) 的数据，\(N \le 10^5,M \le 2 \times 10^5\)
题目分析：
最短路计数显然可以想到 \(dp\)，如果只是计数最短路的话显然，我们假设 \(dis[i]\) 表示到点 \(i\) 的最短路，就是直接设 \(dp[u]\) 表示到 \(u\) 且路径长度为 \(dis[u]\) 的路径条数。
那么这个题肯定需要多加一些维，看上去也就是只能把 \(k\) 扔进去了，也就是直接设 \(dp[u][i]\) 表示到 \(u\) 这个点路径长度为 \(dis[u] + i\) 的路径条数。
转移也是简单的：
\[\begin{aligned}
&dp[u][dis[v] - dis[u] + i - (u,v)] \to dp[v][i] &(u,v) \in E
\end{aligned}
\]
然后就会发现这个转移顺序很难弄，所以就直接记忆化搜索就好了，以及无限解也就是 \(0\) 环的问题也要注意判一下。
代码：
点击查看代码
#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int N = 2e5+5;
int f[N][55],dis[N],n,m,k,MOD;
bool vis[N],ins[N][55],flag;
vector<PII> G1[N],G2[N];
void dij(){
memset(dis,0x3f,sizeof(dis));memset(vis,false,sizeof(vis));
dis[1] = 0;
priority_queue<PII> q;
q.push({-dis[1],1});
while(!q.empty()){
int now = q.top().second;q.pop();
if(vis[now]) continue;
vis[now] = true;
for(PII p : G1[now]){
int to = p.first,val = p.second;
if(dis[to] > dis[now] + val){
dis[to] = dis[now] + val;
q.push({-dis[to],to});
}
}
}
}
int dp(int now,int val){
if(val < 0) return 0;
if(ins[now][val]){ //存在 0 环
flag = true;
return 0;
}
if(f[now][val]) return f[now][val];
ins[now][val] = true;
int res = 0;
for(auto p : G2[now]){
int to = p.first,tmp = p.second;
res = (res + dp(to,dis[now] - dis[to] + val - tmp))%MOD;
if(flag) return 0;
}
ins[now][val] = false;
f[now][val] = res;
return res;
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int T;scanf("%d",&T);
while(T--){
scanf("%d%d%d%d",&n,&m,&k,&MOD);
for(int i=1; i<=m; i++){ //草，竟然写成了 n
int from,to,val;scanf("%d%d%d",&from,&to,&val);
G1[from].push_back({to,val});
G2[to].push_back({from,val});
}
dij();
f[1][0] = 1;
int ans = 0;
for(int i=0; i<=k; i++){
// printf("%d\n",dp(n,i));
ans = (ans + dp(n,i))%MOD;
}
if(flag) printf("-1\n");
else printf("%d\n",ans);
memset(f,0,sizeof(f));memset(ins,0,sizeof(ins));flag = false;
for(int i=1; i<=n; i++) G1[i].clear(),G2[i].clear();
}
return 0;
}