rt，从早上调到现在，评测记录

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef pair<int,int> pii;
const int N=2e5,Inf=1e9;

int T,n,m,K,mod,ex[N+5],ey[N+5],ew[N+5],dp[N+5][60];
int dis[N+5][2],ind[N+5],tpp[N+5];
bool vis[N+5];
struct Nodj{
	int ds,ps;
	inline bool operator <(const Nodj &stmp)const{
		return ds>stmp.ds;
	} 
};
vector<pii>v[N+5];
priority_queue<Nodj>dj;
queue<int>tp;

inline void Dijk(int sps,bool op){
	for(int i=1;i<=n;i++){
		dis[i][op]=((i^sps)?Inf:0);
		vis[i]=0;
	}
	dj.push({0,sps});
	while(!dj.empty()){
		int fq=dj.top().ps;
		dj.pop();
		if(vis[fq])continue;
		vis[fq]=1;
		for(pii i:v[fq]){
			if(dis[i.fi][op]<=dis[fq][op]+i.se)continue;
			dis[i.fi][op]=dis[fq][op]+i.se;
			if(!vis[i.fi])dj.push({dis[i.fi][op],i.fi});
		}
	}
	return;
}

inline void Topo(){
	int ppt=0;
	tp.push(1);
	while(!tp.empty()){
		int fq=tp.front();
		tp.pop();
		tpp[++ppt]=fq;
		for(pii i:v[fq]){
			ind[i.fi]--;
			if(!ind[i.fi])tp.push(i.fi);
		}
	}
	return;
}

inline void solve(){
	cin>>n>>m>>K>>mod;
	for(int i=1;i<=n;i++)v[i].resize(0);
	for(int i=1;i<=m;i++){
		cin>>ex[i]>>ey[i]>>ew[i];
		v[ex[i]].pb({ey[i],ew[i]});
	}
	Dijk(1,0);
	for(int i=1;i<=n;i++)v[i].resize(0);
	for(int i=1;i<=m;i++)v[ey[i]].pb({ex[i],ew[i]});
	Dijk(n,1);
	for(int i=1;i<=n;i++){
		v[i].resize(0);
		ind[i]=0;
	}
	for(int i=1;i<=m;i++){
		if(dis[ex[i]][0]+ew[i]==dis[ey[i]][0]&&dis[ex[i]][0]+ew[i]+dis[ey[i]][1]<=dis[n][0]+K){
			v[ex[i]].pb({ey[i],0});
			ind[ey[i]]++;
		}
		ew[i]=dis[ex[i]][0]+ew[i]-dis[ey[i]][0];
	}
	Topo();
	for(int i=1;i<=n;i++){
		if(!ind[i])continue;
		cout<<"-1\n";
		return;
	}
	for(int i=1;i<=n;i++)for(int j=0;j<=K;j++)dp[i][j]=(i==1&&!j);
	for(int i=0;i<=K;i++){
		for(int j=1;j<=n;j++)for(pii k:v[tpp[j]])dp[k.fi][i]=(dp[k.fi][i]+dp[tpp[j]][i])%mod;
		for(int j=1;j<=m;j++)if(i+ew[j]<=K&&ew[j])dp[ey[j]][i+ew[j]]=(dp[ey[j]][i+ew[j]]+dp[ex[j]][i])%mod;
	}
	int AnS=0;
	for(int i=0;i<=K;i++)AnS=(AnS+dp[n][i])%mod;
	cout<<AnS<<'\n';
	return;
}

signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--)solve();
	return 0;
} 

关注用小号给。