RT，这个题在 dp 的时候顺序应该怎么样才是对了，我直接用 tarjan 的 dfn 不行，然后用拓扑排序的 dfn 还是不行。。。

思路是 tarjan 判环，然后 dp 部分跟各种题解的基本一样。

#include<bits/stdc++.h> 
#define int long long
#define inf 0x3f3f3f3f
using namespace std;
int read(){
	bool f=1;
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=0;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)-48+c;
		c=getchar();
	}
	return f?x:x*-1;
}
char cr[200];int tt;
inline void print(register int x,register char k='\n') {
    if(!x) putchar('0');
    if(x < 0) putchar('-'),x=-x;
    while(x) cr[++tt]=x%10+'0',x/=10;
    while(tt) putchar(cr[tt--]);
    putchar(k);
}
const int maxn=123333;
struct node{
	int to,val;
	friend bool operator <(node a,node b){
		return a.val>b.val;
	}
}tmp;
vector<node>e[maxn][2],e0[maxn];
int T,n,m,k,lim,p,ans,tot,top;
int in[maxn],id[maxn],dfn[maxn],st[maxn],lg[maxn];
int f[maxn][52],dis[maxn][2],low[maxn],sd[maxn];
bool vis[maxn][3],tag[maxn],flag;
void tarjan(int x){
    low[x]=dfn[x]=++tot;lg[x]++;
    st[++top]=x;vis[x][2]=1;
    for(node t:e0[x]){
        int v=t.to;
        if (!dfn[v]){
        	tarjan(v);
        	low[x]=min(low[x],low[v]);
    	}
        else if (vis[v]){
            low[x]=min(low[x],dfn[v]);
        }
    }
    if(dfn[x]==low[x]){
        int y;
        while(y=st[top--]){
            sd[y]=x;
            vis[y][2]=0;
            if(x==y) break;
            lg[x]+=lg[y];
        }
    }
}
void dij(int s,int o){
	priority_queue<node> q;
	dis[s][o]=0;
	tmp.to=s;tmp.val=0;
	q.push(tmp);
	while(!q.empty()){
		tmp=q.top();q.pop();
		int u=tmp.to;
		if(vis[u][o]) continue;
		vis[u][o]=1;
		for(node t:e[u][o]){
			int v=t.to;
			int w=t.val;
			if(dis[v][o]<=dis[u][o]+w) continue;
			dis[v][o]=dis[u][o]+w;
			tmp.to=v;tmp.val=dis[v][o];
			q.push(tmp);
		}
	}
}
void init(){
	flag=ans=tot=0;
	memset(f,0,sizeof(f));
	memset(lg,0,sizeof(lg));
	memset(sd,0,sizeof(sd));
	memset(id,0,sizeof(id));
	memset(tag,0,sizeof(tag));
	memset(vis,0,sizeof(vis));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=n;i++){
		e[i][0].clear();
		e[i][1].clear();
		e0[i].clear();
	}
}
bool cmp(int x,int y){
    if(dis[x][0]==dis[y][0])return dfn[x]<dfn[y];
    return dis[x][0]<dis[y][0];
}
void topo(){
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(in[i]==0&&tag[i]){
			q.push(i);
		}
	}
	while(!q.empty()){
		int u=q.front();q.pop();
		dfn[u]=++tot;
		for(node t:e0[u]){
			int v=t.to;
			in[v]--;
			if(!in[v]){
				q.push(v);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(!in[i]) continue;
		dfn[i]=++tot;
	}
}
signed main(){
	T=read();
	while(T--){
		init();
		n=read();m=read();k=read();p=read();
		priority_queue<node> q;
		for(int i=1;i<=m;i++){
			int u=read(),v=read(),w=read();
			tmp.to=v;tmp.val=w;e[u][0].push_back(tmp);
			tmp.to=u;e[v][1].push_back(tmp);
			if(w==0){
				tmp.to=v;e0[u].push_back(tmp);
				tag[u]=1;
				in[v]++;
			}
		}
		dij(1,0);dij(n,1);
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;i++){
			if(tag[i]&&!dfn[i]) tarjan(i);
		}
		lim=dis[n][0]+k;
		for(int i=1;i<=n;i++){
			if(tag[i]&&lg[sd[i]]>1&&dis[i][0]+dis[i][1]<=lim){
				flag=1;
			}
		}
		if(flag){
			print(-1);
			continue;
		}
		for(int i=1;i<=n;++i){
			id[i]=i;
		}
		tot=0;
		memset(dfn,0,sizeof(dfn));
		topo();
        sort(id+1,id+n+1,cmp);
        f[1][0]=1%p;
        for(int j=0;j<=k;j++){
            for(int t=1;t<=n;t++){
                int u=id[t];
                if(!f[u][j]){
                	continue;	
				}
                for(node d:e[u][0]){
                    int v=d.to;
					int w=dis[u][0]+j+d.val-dis[v][0];
                    if(w<=k){
                    	f[v][w]=(f[v][w]+f[u][j])%p;
					}
                }
            }
            ans=(ans+f[n][j])%p;
        }
        print(ans);
	}
	return 0;
}

调的我好累/kk