传送门

翻了翻往年的$NOIP$题，终于找到一道可做的了$QwQ$

肯定要先跑个最短路。

先不管无解。第一反应是记忆化搜索，搜索状态为当前节点和已经走的距离。

显然是不行的，已经走的距离上界太大，数组开不下。

注意到$K$贼小，可以把$K$当做状态。

于是状态就改为当前节点和与最短路的差距。

显然，根据最短路的性质，走边$edge(x,y)$会导致差距增大$dis_x+edge(x,y).len-dis_y$（$dis$是最短路）

依此记忆化搜索即可。同时要注意，搜到点$n$不能停止，可能通过往回走绕几圈回来也是合法的。（蒟蒻因为这个取得了30分的好成绩）

再来处理无解。满足无解的条件：

  1. 存在$0$环
  2. 从起点经过$0$环到终点存在一条长度小于等于$dis_n+K$的路径

判环我只会Tarjan

反向建图跑最短路，然后依次对位于$0$环的点判断$dis(1,x)+dis(n,x)$是否小于等于$dis(1,n)+K$。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

#define maxn 100005
#define inf 0x3f3f3f3f

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int dis[maxn],disn[maxn],H[maxn],h[maxn],f[maxn][51],sta[maxn],seg[maxn],low[maxn],top,n,m,k,mod,num,all;
bool vis[maxn],zero[maxn];
priority_queue<pair<int,int> >q;
struct edge{
    int pre,to,l;
}e[maxn<<1],E[maxn<<1];
//大写的都是反向建的边
inline void add(int from,int to,int l){
    e[++num].pre=h[from],h[from]=num,e[num].to=to,e[num].l=l;
    E[num].pre=H[to],H[to]=num,E[num].to=from;
}
void DJ(){
    memset(dis,0x3f,sizeof dis);
    dis[1]=0,q.push(make_pair(0,1));
    while(!q.empty()){
        int x=q.top().second;
        q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(register int i=h[x];i;i=e[i].pre)
            if(dis[e[i].to]>dis[x]+e[i].l)q.push(make_pair(-(dis[e[i].to]=dis[x]+e[i].l),e[i].to));
    }
}
void reDJ(){
    memset(disn,0x3f,sizeof disn);
    disn[n]=0,q.push(make_pair(0,n));
    while(!q.empty()){
        int x=q.top().second;
        q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(register int i=H[x];i;i=E[i].pre)
            if(disn[E[i].to]>disn[x]+E[i].l)q.push(make_pair(-(disn[E[i].to]=disn[x]+E[i].l),E[i].to));
    }
}//反向最短路
void TJ(int node){
    vis[node]=1,sta[++top]=node;
    seg[node]=low[node]=++all;
    int x;
    for(register int i=h[node];i;i=e[i].pre){
        if(e[i].l)continue;//只跑0边判0环
        x=e[i].to;
        if(!seg[x])TJ(x),low[node]=min(low[node],low[x]);
        else if(vis[x])low[node]=min(low[node],seg[x]);
    }
    if(seg[node]==low[node]){
        if(sta[top]!=node)zero[node]=1;
        while(sta[top]!=node)vis[sta[top]]=0,zero[sta[top--]]=1;
        --top,vis[node]=0;
    }
}
int dfs(int node,int delta){
    if(delta>k)return 0;//差距超出限制不合法
    if(~f[node][delta])return f[node][delta];
    f[node][delta]=(node==n);//到了终点就有1种方案
    int x;
    for(register int i=h[node];i;i=e[i].pre){
        x=e[i].to;
        f[node][delta]+=dfs(x,delta+dis[node]+e[i].l-dis[x]);
        if(f[node][delta]>=mod)f[node][delta]%=mod;
    }
    return f[node][delta];
}
int main(){
    int t=read(),x,y;
    while(t--){
        n=read(),m=read(),k=read(),mod=read();
        memset(seg,0,sizeof seg);
        memset(zero,0,sizeof zero);
        memset(h,0,sizeof h);
        memset(H,0,sizeof H),num=0,all=0;
        memset(vis,0,sizeof vis);
        while(m--)x=read(),y=read(),add(x,y,read());
        for(register int i=1;i<=n;++i)
            if(!seg[i])TJ(i);
        reDJ();
        memset(vis,0,sizeof vis);
        DJ();
        for(register int i=1;i<=n;++i)
            if(zero[i]&&dis[i]+disn[i]<=dis[n]+k)goto Bad_Option;
        memset(f,-1,sizeof f);
        printf("%d\n",dfs(1,0));//初始的差距为0
        continue;
Bad_Option:
        puts("-1");
    }
}