RT，目前 $70$ 分， TLE #11,#12,#13

本人使用 tarjan 做的这个题（

#include<iostream>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
ll t,n,m,k,mod,vr,u[200005],dis2[100005],sz[100005],f[100005][55],in[100005][55],bel[200005],v[200005],w[200005],dis[100005],low[100005],dfn[100005],vis[100005],c[100005];
vector<pair<int,int> > G[100005],T[100005],L[100005][55];
vector<int> H[100005];
stack<int> s;
priority_queue<pair<ll,int> > q;
queue<pair<int,int> > q2;
void dfs(ll x){
	low[x]=dfn[x]=++vr;
	s.push(x);
	vis[x]=1;
	for(ll i=0;i<H[x].size();i++){
		ll to=H[x][i];
		if(!dfn[to]){
			dfs(to);
			low[x]=min(low[x],low[to]);
		}
		else if(vis[to]){
			low[x]=min(low[x],dfn[to]);
		}
	}
	if(low[x]==dfn[x]){
		while(!s.empty()){
			ll cur=s.top();
			s.pop();
			bel[cur]=x;
			sz[x]++;
			vis[cur]=0;
			if(cur==x){
				break;
			}
		}
	}
}
int main(){
	cin>>t;
	while(t--){
		cin>>n>>m>>k>>mod;
		for(ll i=1;i<=n;i++){
			G[i].clear();
			T[i].clear();
			H[i].clear();
			dis[i]=dis2[i]=1e17;
			vis[i]=sz[i]=bel[i]=dfn[i]=low[i]=0;
		}
		dis[1]=vr=0;
		for(ll i=1;i<=m;i++){
			cin>>u[i]>>v[i]>>w[i];
			G[u[i]].push_back({v[i],w[i]});
			T[v[i]].push_back({u[i],w[i]});
			if(!w[i]){
				H[u[i]].push_back(v[i]);
			}
		}
		q.push({-dis[1],1ll});
		while(!q.empty()){
			ll cur=q.top().second;
			q.pop();
			if(vis[cur]){
				continue;
			}
			vis[cur]=1;
			for(ll i=0;i<G[cur].size();i++){
				ll to,v;
				to=G[cur][i].first;
				v=G[cur][i].second;
				if(dis[to]>dis[cur]+v){
					dis[to]=dis[cur]+v;
					q.push({-dis[to],to});
				}
			}
		} 
		for(ll i=1;i<=n;i++){
			c[i]=dis[i];
			vis[i]=0;
		}
		dis2[n]=0;
		q.push({-dis2[n],n});
		while(!q.empty()){
			ll cur=q.top().second;
			q.pop();
			if(vis[cur]){
				continue;
			}
			vis[cur]=1;
			for(ll i=0;i<T[cur].size();i++){
				ll to,v;
				to=T[cur][i].first;
				v=T[cur][i].second;
				if(dis2[to]>dis2[cur]+v){
					dis2[to]=dis2[cur]+v;
					q.push({-dis2[to],to});
				}
			}
		} 
		for(ll i=1;i<=n;i++){
			vis[i]=0;
		}
		for(ll i=1;i<=n;i++){
			for(ll j=0;j<=k;j++){
				in[i][j]=f[i][j]=0;
				L[i][j].clear();
			}
			if(!dfn[i]){
				dfs(i);
			}
		}
		for(ll i=1;i<=m;i++){
			if(bel[u[i]]!=bel[v[i]]){
				for(ll j=0;j<=k;j++){
					if(c[u[i]]!=1e17&&c[v[i]]!=1e17&&c[u[i]]+w[i]+j-c[v[i]]<=k&&c[u[i]]+w[i]+j-c[v[i]]>=0){
						L[bel[u[i]]][j].push_back({bel[v[i]],c[u[i]]+w[i]+j-c[v[i]]});
						in[bel[v[i]]][c[u[i]]+w[i]+j-c[v[i]]]++;
					}
				}
			}
		}
		f[bel[1]][0]=1;
		while(!q2.empty()){
			q2.pop();
		}
		for(ll i=1;i<=n;i++){
			for(ll j=0;j<=k;j++){
				if(!in[i][j]){
					q2.push({i,j});
				}
			}
		}
		while(!q2.empty()){
			ll cur=q2.front().first,cur2=q2.front().second;
			q2.pop();
			for(ll i=0;i<L[cur][cur2].size();i++){
				ll tox,toy;
				tox=L[cur][cur2][i].first;
				toy=L[cur][cur2][i].second;
				f[tox][toy]=(f[tox][toy]+f[cur][cur2])%mod;
				in[tox][toy]--;
				if(!in[tox][toy]){
					q2.push({tox,toy});
				}
			}
		}
		ll ans=0,flg=1;
		for(ll i=0;i<=k;i++){
			ans=(ans+f[bel[n]][i])%mod;
		}
		//cout<<endl<<endl;
		for(ll i=1;i<=n;i++){
		//	cout<<sz[i]<<" "
			if(sz[i]>=2&&dis2[i]!=1e17&&dis[i]!=1e17&&dis[n]!=1e17&&dis[i]+dis2[i]<=dis[n]+k){
				flg=0;
				break;
			}
		}
	//	cout<<endl<<endl;
		if(!flg){
			cout<<-1<<endl;
		}
		else{
			cout<<ans<<endl;
		}
	}
	return 0;
}