题目描述

策策同学特别喜欢逛公园。 公园可以看成一张 \(N\)个点\(M\) 条边构成的有向图，且没有自环和重边。其中 1号点是公园的入口，N号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。

策策喜欢新鲜的事物，他不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，他不希望每天在逛公园这件事上花费太多的时间。如果1号点到N号点的最短路长为\(d\)，那么策策只会喜欢长度不超过d+K的路线。

策策同学想知道总共有多少条满足条件的路线，你能帮帮他吗？

为避免输出过大，答案对 P取模。

如果有无穷多条合法的路线，请输出 −1。
[输入格式]

第一行包含一个整数 T, 代表数据组数。
接下来 T 组数据，对于每组数据：
第一行包含四个整数 N,M,K,P, 每两个整数之间用一个空格隔开。
接下来 M行，每行三个整数 u,v,w,代表编号为 u,v的点之间有一条权值为w的有向边，每两个整数之间用一个空格隔开。

[输出格式]

输出文件包含 T 行，每行一个整数代表答案。

对于 100% 的数据：1<=T<=5,1<=N<=100000,1≤P≤1000000000,1≤u,v≤N,0<=w<=1000，1<=K<=50,

数据保证：至少存在一条合法的路线.

作为NOIP 的压轴题,刚看到题就知道怎么DP的我写了30分钟愣是写不出来.
是个和Orange♂Good或者其他老师学过~性~信竞的正常人一看数据就知道这题肯定是DP，枚举K（不然人家干嘛给你那么小的K），dp[i][j]=从1到i，比最短路多走j的路径条数，显然
dp[i][j]=∑dp[x][dis[i]−dis[x]+j−edge(i,x)](1≤j≤k),
其中x->i有路
于是乎再加个SPFA判负环这道简单的题就出来啦！！！
代码极其简单：

#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>
#include <algorithm>
//反正都include了总没错
//NOIP时最好别用BITS，否则爆0都没人诉苦
using namespace std;
#define int long long//一时define一时爽，一直define一直爽
#define MAX1 200001
#define MAX2 800001
int loca[MAX1],nxt[MAX2],to[MAX2],len[MAX2],top1;
int Loca[MAX1],Nxt[MAX2],To[MAX2],Len[MAX2],top2;
int dis[MAX1],dis2[MAX2],vis2[MAX1][55];
int dp[MAX1][55],vis[MAX1],zihuan,u,v,w,t,n,m,k,p,ans;
void push1(int u,int v,int w) {
    nxt[++top1]=loca[u];loca[u]=top1;to[top1]=v;len[top1]=w;//正常边 
}
void push2(int u,int v,int w) {
    Nxt[++top2]=Loca[u];Loca[u]=top2;To[top2]=v;Len[top2]=w;//反向边,dp用 
}
void SPFA() {//顺便问下，SPFA的中文名字是什么？？？
    vis[1]=1;
    dis[1]=0;
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int x=q.front();
        q.pop();
        for (int i=loca[x];i;i=nxt[i]) {
            int y=to[i];
            if (dis[y] > dis[x] + len[i]) {
                dis[y] = dis[x] + len[i];
                if (!vis[y]) {
                    vis[y] = 1;
                    q.push(y);
                }
            }
        }
        vis[x] = 0;
    }
}
int dfs(int c, int now) {
    if(dp[c][now]!=-1) return dp[c][now];
    vis2[c][now] = 1;
    dp[c][now] = 0;
    for (int i=Loca[c];i;i = Nxt[i]) {
        int xibo=dis[c]-dis[To[i]]+now-Len[i];//zzy不知道会不会打我QWQ
        if (xibo<0) continue;
        if (vis2[To[i]][xibo]) {
            zihuan = 1;
            return 0;
        }
        dp[c][now]+=dfs(To[i],xibo);
        dp[c][now]%=p;
    }
    vis2[c][now] = 0;
    return dp[c][now];
}
void init(){
    memset(loca,0,sizeof(loca));
    memset(Loca,0,sizeof(Loca));
    memset(dp,-1,sizeof(dp));
    memset(vis2,0,sizeof(vis2));
    memset(vis,0,sizeof(vis));
    memset(dis,0x7f,sizeof(dis));
    zihuan=ans=top1=top2=0;
}
#undef int
int main() {
    #define int long long
    cin>>t;
    for(int j=1;j<=t;j++){
        init();
        cin>>n>>m>>k>>p;
        for(int i=1;i<=m;i++) cin>>u>>v>>w,push1(u,v,w),push2(v,u,w);
        SPFA();
        dp[1][0]=1;
        for(int i=0;i<=k;i++)ans+=dfs(n,i),ans%=p;
        dfs(n,k+1);
        if(zihuan)cout<<-1<<endl;
        else cout<<ans<<endl;
    }
}