<h1>题意描述</h1>

给定一张无向图，定义 $ S $ 为 $ 1 $ 到 $ N $ 的最短路，求该无向图 $ 1 $ 到 $ N $ 的路径中长度小于等于 $ S+K $ 的方案。

题目链接

推荐大家去 uoj 多交一些题目，上面有很多 hack 数据。（像我之前认为 dij 就是 spfa+priority_queue）。

<h1>解题报告</h1>

这一题我们首先一定要跑一遍从 $n$ 到 $1$ 的最短路，记录下 $n$ 到 $i$ 的最短路径长度 $dis_i$

我们考虑动态规划。最长为 $N+k$ 可以理解为你可以多跑长度 $k$。

这样我们写一个 dfs 来搜索，然后无脑记忆化一下。

设 $f[v][i]$ 表示到第 $v$ 个点，走目前的路+之后走最短路到达终点的花费大于最短路不超过 $k$ 的路径条数。

深搜到每一个点的时候如果这一个点是 $n$ 就当前状态记录的答案 $ +1$。枚举这个点指向的点 $next$ 和出边 $w$，转移有 $f[v][i] \to f[next][dis_{next}+w-dis_v]​$ 。

为什么从 $n$ 跑到 $1$ 的原因就是避免掉那些走不到终点的点也加入状态。

然后判断无限多解。只需要一个状态在同一条路径中出现了两次就有无限多种解了。

<h3>代码</h3>

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 100000 + 5;
const int MAXM = 200000 + 5;

int N,M,K,P;

struct Node{
    struct Edge *firstEdge;
    int dist,num;
    bool used;
}node[MAXN],rnode[MAXN];

struct Edge{
    Node s,t;
    int w;
    Edge *next;
}pool[MAXM<<1],*frog = pool;

Edge New(Node s,Node *t,int w){
    Edge *ret = ++frog;
    ret->s = s;ret->t = t;ret->w = w;
    ret->next = s->firstEdge;
    return ret;
}

inline void add(int u,int v,int w){
    node[u].firstEdge = New(&node[u],&node[v],w);
    rnode[v].firstEdge = New(&rnode[v],&rnode[u],w);
}

#define P std::pair<int,Node *>
#define MP std::make_pair

inline void dij(){
    std::priority_queue<P,std::vector<P>,std::greater<P> >q;
    FOR(i,1,N){
        node[i].num = rnode[i].num = i;
        rnode[i].dist = INT_MAX;
        rnode[i].used = false;
    }
    q.push(MP(rnode[N].dist=0,&rnode[N]));
    while(!q.empty()){
        Node *v = q.top().second;q.pop();
        if(v->used) continue;
        v->used = true;
        for(Edge *e = v->firstEdge;e;e = e->next){
            if(e->t->dist > v->dist + e->w){
                e->t->dist = v->dist + e->w;
                q.push(MP(e->t->dist,e->t));
            }
        }
    }
}

int fMAXN;
int visMAXN;
int ha;

int dfs(Node *v,int k){
    if(visv->num) return -1;
    if(fv->num) return fv->num;
    visv->num = true;
    fv->num = (v->num == N) ? 1 : 0;
    for(Edge *e = v->firstEdge;e;e = e->next){
        int t = rnode[e->t->num].dist+e->w-rnode[v->num].dist;
        if(t <= k && t >= 0){
            int res = dfs(e->t,k-t);
            if(res == -1) return fv->num = -1;
            fv->num = (fv->num + res)%ha;
        }
    }
    visv->num = false;
    return fv->num;
}

inline void Solve(){
    CLR(f,0);CLR(vis,false);
    frog = pool;
    scanf("%d%d%d%d",&N,&M,&K,&ha);
    CLR(node,0);CLR(rnode,0);
    FOR(i,1,M){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    dij();
    int ans = dfs(&node[1],K);
    printf("%dn",ans);
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}