vector 存图,T最后三个点,本地3.5s

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+5;
namespace PandaIO{
using ll=long long;
template<typename T>
concept intT=std::is_signed<T>::value;
template<typename T>
concept unsignedT=std::is_unsigned<T>::value;
char buf[1<<20],*p1,*p2;
#define getchar() (p1==p2?(p2=buf+fread(p1=buf,1,1<<20,stdin),p1==p2?EOF:*p1++):*p1++)
int w=5;inline void setw(int x){w=x;return;}
template<typename T>inline void read(T &x){std::cin>>x;return;}
template<unsignedT T>inline void read(T &x){
  x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();
		while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48),c=getchar();}return;}
template<intT T>inline void read(T &x){
  x=0;bool f=false;char c=getchar();while(c<'0'||c>'9')
    {f|=c=='-',c=getchar();}while(c>='0'&&c<='9')
    {x=(x<<3)+(x<<1)+(c^48),c=getchar();}x=f?-x:x;return;}
template<>inline void read<double>(double &x){
  x=0;double y=1;bool f=false,g=false;char c=getchar();
  while(c<'0'||c>'9') f|=c=='-',c=getchar();
  while((c>='0'&&c<='9')||c=='.'){if(c=='.'){g=true,c=getchar();
    continue;}if(g) y/=10,x+=(c^48)*y;else x=x*10+(c^48);c=getchar();}
  x=f?-1*x:x;return;}
template<>inline void read<char>(char &x){x=getchar();
  while(x==' '||x=='\n'){x=getchar();}return;}
template<typename T>inline void write(T x){std::cout<<x;return;}
template<unsignedT T>inline void write(T x){
  if(x/10) write(x/10);putchar((x%10)^48);return;}
template<intT T>inline void write(T x){
  if(x<0){putchar('-');x=-x;}if(x/10) write(x/10);
  putchar((x%10)^48);return;}
template<>inline void write<double>(double x){
  std::cout<<std::fixed<<std::setprecision(w)<<x;return;}
template<>inline void write<std::string>(std::string x){
  for(int i=0;i<(int)x.size();++i){putchar(x[i]);}return;}
template<>inline void write<char>(char x){putchar(x);return;}
template<>inline void write<char*>(char *x){
	for(int i=0;x[i];++i){putchar(x[i]);}return;}
template<typename T,typename... S>inline void read(T &x,S &...y){
  read(x),read(y...);return;}
template<typename T,typename... S>inline void write(T x,S... y){
  write(x),write(y...);return;}
}using PandaIO::read;using PandaIO::write;using PandaIO::setw;
int T,n,m,k,P,deg[N],dist[N],dp[N*55];
struct Edge{int y,z;};bool v[N*55],f;
vector<Edge> G[N];
vector<int> R[N*55];
inline void Dijkstra(){
	priority_queue<pair<int,int>> q;
	memset(v,false,sizeof v);
	memset(dist,0x3f,sizeof dist);
	q.push({0,1});dist[1]=0;
	while(q.size()){
		int x=q.top().second;q.pop();
		if(v[x]) continue;
		v[x]=true;
		for(Edge i:G[x]){
			int y=i.y,z=i.z;
			if(dist[x]+z<dist[y]){
				dist[y]=dist[x]+z;
				q.push({-dist[y],y});
			}
		}
	}
	return;
}
inline void dfs(int x){
	if(f) return;
	if(x==1) dp[x]=1;
	for(int y:R[x]){
		if(v[y]){f=true;break;}
		if(!dp[y]){
			v[y]=true;
			dfs(y);
			v[y]=false;
		}
		dp[x]=(0ll+dp[x]+dp[y])%P;
	}
	return;
}
signed main(){
	// freopen("P3953_11.in","r",stdin);
	// freopen("course.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		read(n,m,k,P);
		memset(deg,0,sizeof deg);
		for(int i=1;i<=n;++i) G[i].clear();
		for(int i=1;i<=n*51;++i) R[i].clear();
		for(int i=1,x,y,z;i<=m;++i){
			read(x,y,z);
			G[x].push_back((Edge){y,z});
		}
		Dijkstra();
		for(int i=0;i<=k;++i) for(int x=1;x<=n;++x){
			for(Edge e:G[x]){
				int y=e.y,z=e.z,delta=dist[x]+z-dist[y];
				if(i+delta>k||delta<0) continue;
				R[(i+delta)*n+y].push_back(i*n+x);
			}
		}
		memset(dp,0,sizeof dp);
		memset(v,false,sizeof v);
		int ans=0;f=false;
		for(int i=0;i<=k;++i){
			v[i*n+n]=true;
			dfs(i*n+n);
			v[i*n+n]=false;
			if(f){puts("-1");goto END;}
			ans=(0ll+ans+dp[i*n+n])%P;
		}
		write(ans,'\n');
		END:;
	}
	cout<<clock();
	return 0;
}

怎么办?怎么办?怎么办?怎么办?