提交了好多次，每次都是随机在最后 3 个点中 TLE ……
这是最后一次提交的代码，语言标准 C++ 11 才过，换回 C++ 98 继续TLE ……

#include <cstring>
#include <cstdio>
#include <cctype>
#include <ext/pb_ds/priority_queue.hpp>

int readInt() {
    int temp = 0;
    char ch = '\0';
    while (!isdigit(ch = getchar()))
        continue;
    do
        temp = temp * 10 + ch - '0';
    while (isdigit(ch = getchar()));
    return temp;
}

struct HeapNode;
typedef __gnu_pbds::priority_queue<HeapNode> Heap;
typedef Heap::point_iterator Iterator;
typedef long long LL;

struct Point {
    int head;
    int dist;
    bool vis;

    Point() : head(0), dist(0X3F3F3F3F), vis(false) {}
} posi_pts[100001], nega_pts[100001], final_pts[100001];
struct Path {
    int next, from, to, cost;

    Path(int n = 0, int u = 0, int v = 0, int c = 0) : next(n), from(u), to(v), cost(c) {}
} posi_g[200001], nega_g[200001], final_g[200001];
const Point plain_point;
const Path plain_path;

struct HeapNode {
    int id;
    int dist;

    HeapNode(int a, int b) : id(a), dist(b) {}

    inline bool operator< (const HeapNode &hp) const {
        if (dist != hp.dist) return dist > hp.dist;
        return id > hp.id;
    }
};

LL dp[51][100001];
Iterator it[100001];
bool vis[51][100001], check[51][100001], res;
int ptr, n, m, p, k;
int min_dist;

inline void setPath(int u, int v, int c) {
    ++ptr;
    posi_g[ptr] = Path(posi_pts[u].head, u, v, c), posi_pts[u].head = ptr;
    nega_g[ptr] = Path(nega_pts[v].head, v, u, c), nega_pts[v].head = ptr;
}
inline void setFinalPath(int u, int v, int c) {
    final_g[++ptr] = Path(final_pts[u].head, u, v, c), final_pts[u].head = ptr;
}

void Dijkstra(int s, Point *pt, Path *ph) {
    static Heap q;
    q.push(HeapNode(s, 0));
    pt[s].dist = 0;
    for (int i = 1; i <= n; ++i)
        it[i] = Iterator();
    while (!q.empty()) {
        HeapNode p = q.top();
        q.pop(), pt[p.id].vis = true;
        for (int i = pt[p.id].head; i; i = ph[i].next) {
            int x = ph[i].to;
            LL cost = ph[i].cost;
            if (pt[x].vis) continue;
            if (pt[x].dist > p.dist + cost) {
                pt[x].dist = p.dist + cost;
                if (it[x] == 0)
                    it[x] = q.push(HeapNode(x, pt[x].dist));
                else
                    q.modify(it[x], HeapNode(x, pt[x].dist));
            }
        }
    }
}

LL DFS(int dist, int pos) {
    if (check[dist][pos])
        return dp[dist][pos];
    if (vis[dist][pos])
        return res = true;
    vis[dist][pos] = true;
    for (int i = final_pts[pos].head; i; i = final_g[i].next) {
        int x = final_g[i].to, c = final_g[i].cost;
        if (dist + c > k) continue;
        dp[dist][pos] += DFS(dist + c, x);
        dp[dist][pos] %= p;
    }
    vis[dist][pos] = false;
    check[dist][pos] = true;
    return dp[dist][pos];
}

int main() {
    int case_cnt = readInt();
    while (case_cnt--) {
        n = readInt(), m = readInt(), k = readInt(), p = readInt();
        for (int i = 1; i <= m; ++i) {
            int u = readInt(), v = readInt(), c = readInt();
            setPath(u, v, c);
        }
        Dijkstra(1, posi_pts, posi_g);
        Dijkstra(n, nega_pts, nega_g);
        min_dist = posi_pts[n].dist, ptr = 0;
        for (int i = 1; i <= m; ++i) {
            int u = posi_g[i].from, v = posi_g[i].to;
            if (posi_pts[u].dist + nega_pts[u].dist <= min_dist + k
             && posi_pts[u].dist + nega_pts[v].dist + nega_g[i].cost <= min_dist + k)
                setFinalPath(u, v, posi_pts[u].dist + nega_g[i].cost - posi_pts[v].dist);
        }
        for (int i = 0; i <= k; ++i)
            dp[i][n] = 1;
        int ans = DFS(0, 1);
        printf("%lld\n", (res ? -1LL : ans));
        for (int i = 0; i <= k; ++i)
        for (int j = 1; j <= n; ++j)
            dp[i][j] = 0;
        for (int i = 0; i <= k; ++i)
        for (int j = 1; j <= n; ++j)
            check[i][j] = false;
        for (int i = 1; i <= n; ++i)
            posi_pts[i] = plain_point;
        for (int i = 1; i <= n; ++i)
            nega_pts[i] = plain_point;
        for (int i = 1; i <= n; ++i)
            final_pts[i] = plain_point;
        for (int i = 1; i <= m; ++i)
            posi_g[i] = plain_path;
        for (int i = 1; i <= m; ++i)
            nega_g[i] = plain_path;
        for (int i = 1; i <= m; ++i)
            final_g[i] = plain_path;
       ptr = 0, res = false;
    }
    return 0;
}