发现 \(K\) 很小，不妨设置一个 \(O(NK)\) 的 \(DP\)。

发现可行的最短路必须满足是 \(d <= dis <= d + K\)。

由逆向思维，则是从某点出发，可以消耗 \(K\) 个单位的冗余长度，最终到达 \(n\)。

如何快速的计算出有走这条边冗余长度呢

首先建反向图跑 \(Dijkstra\)，求出 \(dis[i]\) 表示从 \(i\) 到 \(n\) 的最短路距离。

假设有一条边 \((u, v)\)，边长为 \(w\)

那么我现在从 \(u\) 到 \(n\) 的预算距离是 \(dis[v] + w\)，最短距离是 \(dis[u]\)。

那么多走的就是 \(dis[v] + w - dis[u]\)。

设计 \(DP\) 状态表示：

\(f[i][j]\) 表示从 \(i\) 到 \(n\)，以及消耗了 \(j\) 个单位的冗余长度的方案数。

状态转移：

设有边 \((u, v)\)，边长为 \(w\)

则有 \(f[u][j] += f[v][j - (dis[v] + w - dis[u])]\)。

边界 \(f[n][0] = 1\)，其余为 \(0\)。

答案 \(\sum_{i = 0}^{K} f[1][i]\)。

无穷解的判断：

发现有无穷解，当且仅当：

有一个总权为 \(0\) 的环。

我们可以在 \(DP\) 的时候搞一个 \(vis\) 数组判断，就不需要单独判无穷解了。

时间复杂度

整个过程用记忆化搜索实现，由于一共有 \(NK\) 个状态，每个点被枚举 \(K\) 次，即每条边总体被枚举 \(K\) 次。

所以复杂度 \(O(K(N + M))\)。

\(Tips:\)

1. 可能走到 \(n\) 再折回去，所以 $u = n $ 时不能直接 \(return\)
2. 可能存在经过 \(n\) 点的 \(0\) 环，所以到 \(n\) 点时顺便判一下环。

#include <cstdio>

#include <iostream>

#include <cstring>

#include <queue>

#include <vector>

#include <cstdlib>

using namespace std;

typedef pair<int, int> PII;

const int N = 100005, M = 400005, S = 51;

int n, m, K, P, f[N][S], dis[N];

int head[N], rhead[N], numE[2];

bool st[N], vis[N][S], ep = false;

struct E {

    int next, v, w;

}e[M], r[M];

//建图

void inline add(E g[], int h[], int u, int v, int w, int p) {

    g[++numE[p]] = (E) { h[u], v, w };

    h[u] = numE[p];

}

//多组数据初始化

void inline init() {

    ep = false;

    memset(dis, 0x3f, sizeof dis);

    memset(st, false, sizeof st);

    numE[0] = numE[1] = 0;

    memset(head, 0, sizeof head);

    memset(rhead, 0, sizeof head);

    memset(f, -1, sizeof f);

}

// Dijkstra 最短路

priority_queue<PII, vector<PII>, greater<PII> > q;

void inline dijkstra() {

    dis[n] = 0; q.push(make_pair(0, n));

    while(!q.empty()) {

        PII u = q.top(); q.pop();

        if(st[u.second]) continue;

        st[u.second] = true;

        for (int i = rhead[u.second]; i; i = r[i].next) {

            int v = r[i].v;

            if(dis[u.second] + r[i].w < dis[v]) {

                dis[v] = dis[u.second] + r[i].w;

                q.push(make_pair(dis[v], v));

            }

        }

    }

}

//记忆化搜索

int dfs(int u, int j) {

    if(vis[u][j]) { ep = true; return 0; }

    if(f[u][j] != -1) return f[u][j];

    vis[u][j] = true;

    int &val = f[u][j] = 0;

    for (int i = head[u]; i; i = e[i].next) {

        int v = e[i].v, w = e[i].w;

        //消耗的冗余长度折算

        int k = j - (dis[v] + w - dis[u]);

        if(0 <= k && k <= K) (val += dfs(v, k)) %= P;

        if(ep) return 0;

    }

    vis[u][j] = false;

    if(u == n && j == 0) val = 1;

    return val;

}

int main() {

    int T; scanf("%d", &T);

    while(T--) {

        init();

        scanf("%d%d%d%d", &n, &m, &K, &P);

        for (int i = 1, u, v, w; i <= m; i++) {

            scanf("%d%d%d", &u, &v, &w);

            add(e, head, u, v, w, 0); add(r, rhead, v, u, w, 1);

        }

        dijkstra();

        int ans = 0;

        for (int i = 0; i <= K; i++) {

            memset(vis, false, sizeof vis);

            (ans += dfs(1, i)) %= P;

            if(ep) break;

        }

        if(ep) puts("-1");

        else printf("%d\n", ans);

    }

}