考虑一种最简单的状态

设 $f_{v,j}$ 为走到点 $v$ 路线长度恰为 $j$ 的方案数。转移则是枚举从哪个点走过来。

即 $f_{v,j}=\sum f_{u,j-w}$ 设 $u->v$ 边权为 $w$

这么做的状态是非常多的，但是我们可以发现有一个 $k$ 的限制，导致很多第二维状态没有用处。例如设 $1\sim n$ 的最短路为 $d$

对于 $j<d$ 的状态 $j$ 必然为 $0$,实际需要求的也仅仅是 $f_{n,d}+f_{n,d+1}+\dots+f_{n,d+k}$ 只有 $k+1$ 个状态是合法的

对于其余的某个点 $v$ 设到达点 $v$ 的最短路是 $d_v$ 则 $j$ 必须 $j\geq d_v$

同时必须满足 $j\leq d_v+k$

简单证明来说，若走到 $v$ 第二维 $j$ 已经大于 $d_v+k$ 则后续不管怎么走走到 $n$ 的路径长度必然大于 $d+k$

故而对于任意点 $v$ 只需要考虑 $k+1$ 个状态。

重新修改状态，设 $f_{v,j}$ 为从起点走到 $v$ 且路径长度恰好为 $d_v+j$ 的所有路线数量，相当于第二维是最短距离加偏移量。

状态转移：由于第二维寸的是一个偏移量，考虑某个点 $u$ 走到 $v$ ，点 $v$ 此时第二维状态 $j$ ，实际走到 $v$ 的真实距离是 $d_v+j$ 则走到 $u$ 的真是距离应为 $d_v+j-w$，它同时等于 $d_u+x$ ，$x$ 为此时走到 $u$ 的便宜量，则 $x=d_v+j-w-d_u$。即 $f_{v,j}=\sum f_{u,x},x=d_v+j-w-d_u$。

若有环怎么办？

首先对于本题来说，如果存在一条路径走到 $n$ 有环，环上边权和为 $0$ 那么肯定有无限种方案，因此在使用记忆化搜索的同时若出现循环依赖，直接返回负 $1$ 即可。

具体步骤

• 使用最短路算法预处理最短路 $d_i$
• 记忆化搜索搜索 $f_{n,0},f_{n,1},\dots,f_{n,k}$
• 记忆化搜索可以存反图，从终点开始搜索，这是为了保证求解的正确性，因为图中的某些点不一定能到达 $n$ 假如走到一个环，且该环无法到达 $n$ 则导致了后续求解的错误。
• 对于判断是否存在 $0$ 的环路，则看一个状态是否重复访问即可，设置一个判重数组来判断状态是否重复访问。

#include <bits/stdc++.h>
#define ll long long
#define p pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 1e5 + 5;
int n, m, k, mod, d[N], f[N][55];
vector<p> e[N], ne[N];
bool vis[N], flag;
bool instk[N][55];
void dijkstra()
{
    memset(d, 0x3f, sizeof(d));
    memset(vis, 0, sizeof(vis));
    priority_queue<p, vector<p>, greater<p>> q;
    q.push({0, 1});
    d[1] = 0;
    while (q.size())
    {
        auto now = q.top();
        q.pop();
        int u = now.y;
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto road : e[u])
        {
            int v = road.x, w = road.y;
            if (d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                q.push({d[v], v});
            }
        }
    }
}
int dp(int u, int j) // f[b][j] 
{
    if (instk[u][j])
    {
        flag = 1;
        return 0;
    }
    if (f[u][j] != -1) return f[u][j];
    f[u][j] = 0;
    if (u == 1 && j == 0) f[u][j]++;
    instk[u][j] = 1;
    for (auto road : ne[u])
    {
        int v = road.x, w = road.y;
        int x = d[u] + j - w - d[v];
        if (x < 0 || x > k) continue;
        f[u][j] = (f[u][j] + dp(v, x)) % mod;
        if (flag) return 0;
    }
    instk[u][j] = 0;
    return f[u][j];
}
void solve()
{
    cin >> n >> m >> k >> mod;
    for (int i = 1; i <= n; i++) e[i].clear(), ne[i].clear();
    while (m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w}), ne[v].push_back({u, w});
    }
    dijkstra();
    memset(f, -1, sizeof(f));
    int res = 0;
    flag = 0;
    memset(instk, 0, sizeof(instk));
    for (int i = 0; i <= k; i++)
    {
        res = (res + dp(n, i)) % mod;
        if (flag) 
        {
            res = -1;
            break;
        }
    }
    cout << res << "\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

这道题太难了，不会做