题意

求长度$\le$最短路$+k$的路径数

数据范围：$n \le 100000,m \le 200000$

题解

首先需要跑一边最短路找到这个最短路；虽然保证存在$1 \rightarrow n$的路径，但并不是所有的点都能到$n$，所以应跑反向图
用$f[u][i]$表示从$u$到$n$的路径中$\le dis[u][n]+i$的路径数，则答案为$f[1][k]$
对于转移，考虑一条边$u \rightarrow v$，如果选择走这条边，那么到$n$的距离为$$dis[v][n]-dis[u][n]+w$$
那么，对于$u$的所有出边$$f[u][i]=\sum f[v][i-(dis[v][n]-dis[u][n]+w)]$$
题目中提到可能有无穷多条合法的路线，而简单路径的个数有限，那么在此指存在$0$环
对于$0$环的判断，记录一个$vis[u][i]$，当$vis[u][i]$再次被访问时即存在$0$环

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define mp make_pair
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
const int N=100000+10;
const int K=50+5;
int t,n,m,k,p,u,v,w;
int cnt;
int head1[N],head2[N],dis[N],dp[N][K];
bool vis[N][K];
struct edge{
    int nxt,to,w;
} e[N<<2];
inline void add(int *head,int u,int v,int w){
    e[++cnt]=edge{head[u],v,w};
    head[u]=cnt;
}
inline void Dijkstra(){
    priority_queue<pii,vector<pii>,greater<pii> > pq;
    memset(dis,0x3f,sizeof(dis));
    pq.push(mp(0,n));
    dis[n]=0;
    for(;!pq.empty();){
        int d=pq.top().first,u=pq.top().second;
        pq.pop();
        if(d!=dis[u])
            continue;
        for(int i=head2[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(dis[v]>d+e[i].w){
                dis[v]=d+e[i].w;
                pq.push(mp(dis[v],v));
            }
        }
    }
}
int dfs(int u,int k){
    if(vis[u][k])
        return -1;
    if(dp[u][k])
        return dp[u][k];
    vis[u][k]=1;
    dp[u][k]=(u==n);
    for(int i=head1[u];i;i=e[i].nxt){
        int v=e[i].to,d=dis[v]-dis[u]+e[i].w;
        if(d<=k){
            int t=dfs(v,k-d);
            if(t==-1)
                return dp[u][k]=-1;
            (dp[u][k]+=t)%=p;
        }
    }
    vis[u][k]=0;
    return dp[u][k];
}
int main(){
    scanf("%d",&t);
    for(;t--;){
        cnt=0;
        memset(head1,0,sizeof(head1));
        memset(head2,0,sizeof(head2));
        memset(vis,0,sizeof(vis));
        memset(dp,0,sizeof(dp));
        scanf("%d%d%d%d",&n,&m,&k,&p);
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&u,&v,&w);
            add(head1,u,v,w);
            add(head2,v,u,w);
        }
        Dijkstra();
        printf("%d\n",dfs(1,k));
    }
    return 0;
}