代码奇丑勿喷

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int s=0,w=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')w=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')s=(s<<3)+(s<<1)+(c^48),c=getchar();
	return s*w;
}
inline void print(int x)
{
	if(x<0)x=-x,putchar('-');
	if(x>=10)print(x/10);
	putchar(x%10+48);
}
int T,n,m,k,p;
struct node
{
	int u,v,w,next;
}e[2000010],g[10000010],G[10000010],E[10000010];
int eid=1,head[100010],Head[5000010],HEAD[5000010],hd[5000010],in[5000010],vis[5000010],Eid=1,idu=1,idx=1,dis[100010],tp[1000010],f[5000010],id[100010][55],tot,num;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
inline void insert(int u,int v,int w)
{
	e[eid].v=v;
	e[eid].w=w;
	e[eid].next=head[u];
	head[u]=eid++;
}
inline void Insert(int u,int v)
{
	E[Eid].v=v;
	E[Eid].next=HEAD[u];
	HEAD[u]=Eid++;
}
inline void add(int u,int v)
{
	g[idx].u=u;
	g[idx].v=v;
	g[idx].next=Head[u];
	Head[u]=idx++;
}
inline void Add(int u,int v)
{
	G[idu].v=v;
	G[idu].next=hd[u];
	hd[u]=idu++;
}
struct edge
{
	int w,x;
}c[5000010];
int cnt;
bool cmp(edge a,edge b)
{
	return a.w<b.w;
}
queue<int> Q;
int Vis[5000010];
inline void dfs(int u)
{
	vis[u]=1;
	for(int i=Head[u];i;i=g[i].next)
	{
		int v=g[i].v;
		if(vis[v])continue;
		dfs(v);
	}
}
inline void Dfs(int u)
{
	Vis[u]=1;
	for(int i=hd[u];i;i=G[i].next)
	{
		int v=G[i].v;
		if(Vis[v])continue;
		Dfs(v);
	}
}
int main()
{
	T=read();
	while(T--)
	{
		n=read();
		m=read();
		k=read();
		p=read();
		memset(head,0,sizeof(head));
		for(int i=1;i<=tot;i++)Head[i]=hd[i]=HEAD[i]=vis[i]=Vis[i]=in[i]=0;
		memset(f,0,sizeof(f));
		eid=1;
		idx=1;
		idu=1;
		Eid=1;
		tot=0;
		cnt=0;
		for(int i=1;i<=m;i++)
		{
			int u=read(),v=read(),w=read();
			insert(u,v,w);
		}
		memset(dis,0x3f,sizeof(dis));
		memset(id,0,sizeof(id));
		dis[1]=0;
		q.push({0,1});
		num=0;
		while(q.size())
		{
			int u=q.top().second;
			q.pop();
			if(vis[u])continue;
			vis[u]=1;
			tp[++num]=u;
			for(int i=head[u];i;i=e[i].next)
			{
				int v=e[i].v;
				if(dis[v]>dis[u]+e[i].w)
				{
					dis[v]=dis[u]+e[i].w;
					q.push({dis[v],v});
				}
			}
		}
		for(int i=1;i<=n;i++)vis[i]=0;
		for(int x=1;x<=n;x++)
		{
			for(int j=0;j<=k;j++)
			{
				c[++cnt]={dis[x]+j,x};
			}
		}
		sort(c+1,c+cnt+1,cmp);
		for(int l=1;l<=cnt;l++)
		{
			int x=c[l].x,y=c[l].w;
			int j=y-dis[x];
			for(int i=head[x];i;i=e[i].next)
			{
				int v=e[i].v;
				if(y+e[i].w-dis[v]>k)continue;
				if(y+e[i].w-dis[v]<0)
				{
					continue;
				}
				if(id[x][j]==0)id[x][j]=++tot;
				if(id[v][y+e[i].w-dis[v]]==0)id[v][y+e[i].w-dis[v]]=++tot;
				add(id[x][j],id[v][y+e[i].w-dis[v]]);
				Add(id[v][y+e[i].w-dis[v]],id[x][j]);
				in[id[v][y+e[i].w-dis[v]]]++;
			}
		}
		f[id[1][0]]=1;
		for(int i=1;i<=tot;i++)
		{
			if(!in[i])Q.push(i);
		}
		while(Q.size())
		{
			int u=Q.front();
			Q.pop();
			for(int i=Head[u];i;i=g[i].next)
			{
				int v=g[i].v;
				f[v]+=f[u];
				f[v]%=p;
				if(--in[v]==0)
				{
					Q.push(v);
				}
			}
		}
		dfs(id[1][0]);
		tot++;
		for(int i=1;i<=tot;i++)in[i]=0;
		for(int i=0;i<=k;i++)Add(tot,id[n][i]);
		Dfs(tot);
		for(int i=1;i<=idx;i++)
		{
			int u=g[i].u,v=g[i].v;
			if(vis[u]&&Vis[u]&&vis[v]&&Vis[v])
			{
				Insert(u,v);
				in[v]++;
			}
		}
		for(int i=1;i<=tot;i++)
		{
			if(!in[i]&&vis[i]&&Vis[i])
			{
				Q.push(i);
			}
		}
		while(Q.size())
		{
			int u=Q.front();
			Q.pop();
			for(int i=HEAD[u];i;i=E[i].next)
			{
				int v=E[i].v;
				if(--in[v]==0)Q.push(v);
			}
		}
		bool flg=0;
		for(int i=1;i<=tot;i++)
		{
			if(in[i])
			{
				flg=1;
				break;
			}
		}
		if(flg)
		{
			puts("-1");
			continue;
		}
		int ans=0;
		for(int i=0;i<=k;i++)ans=(ans+f[id[n][i]])%p;
		print(ans);
		puts("");
	}
}

上面这是正常代码。

然后我发现这个排序(sort)没用。因为连的状态自然形成了一个拓扑图，直接topsort即可。

但是当我去掉了排序之后（只注释排序）：

我只能获得50分。在看了数据以后，发现一些有解的被判成了-1。

个人反复调试无果，遂求助。