$O(nlogn+nk)$

设$f[x][k]$表示走到点x和dist[x]的差值为k的方案数,使用dijktra处理最短路，然后记忆化搜索即可。

在搜索的过程中如果遇到已有的状态，那么说明存在边权为0的环且一定可以走到终点，说明一定是无限条。

#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=400010,K=55;
#define x first
#define y second
typedef pair<int,int> PII;

int n,m,k,P;
vector<PII> g[N],ng[N]; //g是正向图,ng是反向图
int dist[N],f[N][K]; //dist[]是dijkstra的最短路,f[x][b]表示走到x,和dist[x]差值为b的方案数
bool st[N],in_stk[N][K],is_inf;
//st[]用于dijkstra判重,in_stk[][]用于判断环

void dijkstra() //dijkstra求最短路
{
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    dist[1]=0;
    priority_queue<PII,vector<PII>,greater<PII> > heap;
    heap.push({0,1});
    while(heap.size())
    {
        auto tt=heap.top();
        heap.pop();
        int ver=tt.y;
        if(st[ver]) continue;
        st[ver]=true;
        for(auto t:g[ver])
        {
            if(dist[t.x]>dist[ver]+t.y)
            {
                dist[t.x]=dist[ver]+t.y;
                heap.push({dist[t.x],t.x});
            }
        }
    }
}
int dp(int b,int y)
{
    if(in_stk[b][y]) //在1到n的路径上出现边权为0的环
    {
        is_inf=true;
        return 0;
    }
    int &v=f[b][y];
    if(v!=-1) return v;//已经找到过了
    in_stk[b][y]=true;//标记已经入栈
    v=0;
    if(b==1&&y==0) v++;//起点
    for(auto t:ng[b])
    {
    
        int x=dist[b]+y-t.y-dist[t.x];
        if(x<0||x>k) continue;
        v=(v+dp(t.x,x))%P; //继续往前搜索
        if(is_inf) return 0;
    }
    in_stk[b][y]=false; //清空栈中标记
    return v;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m>>k>>P;
       	for(int i=0;i<N;i++) //清空图
       	{
       		g[i].clear();
       		ng[i].clear();
		}
        while(m--) //建立图
        {
            int a,b,c;
            cin>>a>>b>>c;
            g[a].push_back({b,c});
            ng[b].push_back({a,c});
        }
        dijkstra();
        memset(f,-1,sizeof f); //清空状态数组
        memset(in_stk,0,sizeof in_stk); //清空栈标记
        is_inf=false; //清空环的标记
        int res=0;
        for(int i=0;i<=k;i++)
        {
            res=(res+dp(n,i))%P;
            if(is_inf) break;
        }
        if(is_inf) res=-1;
        cout<<res<<endl;
    }
    return 0;
}