f(i, j)代表从第1个点到第i个点，长度刚好是第1个点到第i个点最短路径的长度加j，路径的数量。如果递归时发现递归到了已经正在递归的点，返回-1。

#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

int T;

int dist[100001];

int f[100001][51];
bool working[100001][51];

int n, m, k, p;

const int INF = 2100000000;

struct Edge {
    int to;
    int len;
};

vector<Edge> graph[100001];
vector<Edge> graph_r[100001];

int get(int node, int l)
{
    int ans = 0;
    if (l < 0 || l > k) return 0;
    if (working[node][l]) {
        working[node][l] = false;
        return -1;
    }
    if (f[node][l] != -1) {
        return f[node][l];
    }
    working[node][l] = true;
    for (int i = 0; i < graph_r[node].size(); i++) {
        Edge e = graph_r[node][i];
        int val = get(e.to, dist[node] + l - dist[e.to] - e.len);
        if (val == -1) {
            working[node][l] = false;
            return -1;
        }
        ans += val;
        if (ans >= p) ans -= p;
    }
    working[node][l] = false;
    if (node == 1 && l == 0) ans++;
    f[node][l] = ans;
    return ans;
}

int work(void)
{
    scanf("%d%d%d%d", &n, &m, &k, &p);
    for (int i = 1; i <= n; i++) {
        graph[i].clear();
        graph_r[i].clear();
    }
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        Edge e;
        e.to = b;
        e.len = c;
        graph[a].push_back(e);
        e.to = a;
        graph_r[b].push_back(e);
    }
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            f[i][j] = -1;
        }
    }
    dist[1] = 0;
    queue<int> que;
    que.push(1);
    while (!que.empty()) {
        int elem = que.front();
        que.pop();
        for (int i = 0; i < graph[elem].size(); i++) {
            if (dist[graph[elem][i].to] > dist[elem] + graph[elem][i].len) {
                dist[graph[elem][i].to] = dist[elem] + graph[elem][i].len;
                que.push(graph[elem][i].to);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= k; i++) {
        int val = get(n, i);
        if (val == -1)
            return -1;
        ans += val;
        if (ans >= p) ans -= p;
    }
    return ans;
}

int main()
{
    scanf("%d", &T);
    for (int i = 1; i <= T; i++) {
        printf("%d\n", work());
    }
    return 0;
}

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
#include <thread>
using namespace std;

namespace dts
{
    typedef long long ll;
    
    struct edge
    {
        ll to,d,next;
        edge()
        {
            to=d=next=0;
        };
        edge(ll tov,ll dv,ll nextv)
        {
            to=tov,d=dv,next=nextv;
        };
    };
    
    ll T;
    ll n,m,t,p,esize,flag;
    ll a[200000+1];
    ll b[200000+1];
    ll c[200000+1];
    ll dis[100000+1];
    ll vis[100000+1];
    ll head1[100000+1];
    ll head2[100000+1];
    ll f[100000+1][50+1+1];
    ll v[100000+1][50+1+1];
    deque<ll> q;
    edge e1[200000+1];
    edge e2[200000+1];
    
    void add(ll x,ll y,ll d)
    {
        esize++;
        e1[esize]=edge(y,d,head1[x]);
        e2[esize]=edge(x,d,head2[y]);
        head1[x]=head2[y]=esize;
    }
    
    void spfa()
    {
        q.clear();
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        dis[1]=0;
        for (vis[1]=1,q.push_back(1);!q.empty();)
        {
            ll now=q.front();
            vis[now]=0,q.pop_front();
            for (ll i=head1[now];i;i=e1[i].next)
            {
                ll to=e1[i].to,d=e1[i].d;
                if (dis[now]+d<dis[to])
                {
                    dis[to]=dis[now]+d;
                    if (!vis[to])
                        vis[to]=1,q.push_back(to);
                }
            }
        }
    }
    
    ll dfs(ll now,ll t)
    {
        if (f[now][t]!=-1)
            return f[now][t];
        v[now][t]=1;
        f[now][t]=0;
        for (ll i=head2[now];i;i=e2[i].next)
        {
            ll to=e2[i].to,d=e2[i].d;
            ll s=dis[now]+t-d-dis[to];
            if (s>=0)
            {
                if (v[to][s])
                    flag=1;
                f[now][t]=(f[now][t]+dfs(to,s))%p;
            }
        }
        v[now][t]=0;
        return f[now][t];
    }
    
    ll work()
    {
        spfa();
        memset(f,-1,sizeof(f));
        f[1][0]=1;
        memset(v,0,sizeof(v));
        ll ans=0;
        for (ll i=0;i<=t&&(!flag);i++)
            ans=(ans+dfs(n,i))%p;
        if (!flag)
            dfs(n,t+1);
        if (flag)
            return -1;
        else
            return ans;
    }
    
    void main()
    {
        while (~scanf("%lld",&T))
            for (ll rp=1;rp<=T;rp++)
            {
                flag=0;
                scanf("%lld%lld%lld%lld",&n,&m,&t,&p);
                esize=0;
                memset(head1,0,sizeof(head1));
                memset(head2,0,sizeof(head2));
                for (ll i=1;i<=m;i++)
                {
                    scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
                    add(a[i],b[i],c[i]);
                }
                printf("%lld\n",work());
            }
    }
}

int main()
{
    dts::main();
}