【正经题解】逛公园

可以先建图（正反都要），跑一遍最短路，在枚举 $0-k$ ，因为 $k$ 比较小枚举按道理是不会超时的，除非时你写错了，跑一遍反图，所有的情况求和，就好了 可是怎么求答案呢： 可以 $dp$ 来做，用 $f$ [ $i$ ][ $j$ ]表示从 $n$ 到 $i$ 的距离 $<$ 最短距离 $+k$ 的方案数，对于每一条边都尝试走，而这个状态可以表示为 $u->v$ : $d$ [ $u$ ] $-d$ [ $v$ ] $+k-len$ [ $u->v$ ];

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int t,d[100001],f[100001][51],n,m,k,p;
bool working[100001][51];
struct node  {
    int to,len;
};
vector<node>head[100001];
vector<node>h[100001];
//这里用两个vector来存图，初始化的时候非常方便
//，强烈建议使用，不容易出错
int dp(int root, int l){	//这才是这道题的奥妙所在
	//root表示到哪个点了，l表当前的k还有多少剩余
    int ans=0;			
//反向跑是因为可以减少跑死胡同的情况增加效率，
//一些不能到达n的路径就可以不用跑了，可以自行画图理解
    if (l<0||l> k) return 0;//这种情况说明答案不合法
    if (working[root][l]) {
//working数组是为了判断‘0’环的情况，
//当其已经为1时代表它已经跑过了，就可以跳出来了
        working[root][l]=false;
        return -1;
    }
    if(f[root][l]!=-1)   
  //f有值了代表求出答案了
		return f[root][l];
    working[root][l]=true;
    for (int i=0;i<h[root].size();i++) {//跑反图
        node e= h[root][i];
        int val=dp(e.to,d[root]+l-d[e.to]-e.len);
//这个表达式，表示用尝试当前这条边替换其中最短路径里的一条边
//来求一个合法的解
        if (val==-1) {
            working[root][l]=false;
            return -1;
        }
        ans=(ans+val)%p;
    }
    working[root][l] = false;	
    if (root==1&&l==0) ans++;
   	//跑到这里是证明这是一个解ans就+1
    f[root][l]=ans;//记录答案
    return ans;
}

int work(){
    scanf("%d%d%d%d", &n, &m, &k, &p);
    for (int i=1;i<=n;i++) {//看，初始化只要几行就好了
        head[i].clear();
        h[i].clear();
    }
	int a, b, c;
    for (int i=1;i<= m;i++) {//存图
        scanf("%d%d%d",&a,&b,&c);
        node  e;
        e.to=b;	e.len=c;
        head[a].push_back(e);
        e.to=a;				//反图
        h[b].push_back(e);
    }
    memset(d,0x3f,sizeof(d));		//spfa
    memset(f,-1,sizeof(f));	//记得初始化，否则会wa声一片
    queue<int>q;
    q.push(1);	d[1]=0;
    while (!q.empty()) {
        int x=q.front();
        q.pop();
        for (int i=0;i<head[x].size();i++) {
            if (d[head[x][i].to]>d[x]+head[x][i].len) {
                d[head[x][i].to]=d[x]+head[x][i].len;
                q.push(head[x][i].to);
            }
        }
    }
    int ans=0;
    for (int i=0;i<=k;i++) {		//dp 枚举k：0-k, 
        int val=dp(n,i);			//求和后就是答案
        if (val==-1)   return -1;
        ans=(ans+val)%p;
    }
    return ans;
}

int main(){
    scanf("%d", &t);
    while(t--) printf("%d\n", work());
    return 0;
}