题解

题目分析

这是一道算法题目，需要根据具体题目要求进行求解。

解题思路

1. 问题分析

• 仔细阅读题目描述，理解题目要求
• 分析输入输出格式和约束条件
• 确定需要使用的算法和数据结构

2. 算法选择

• 根据题目特点选择合适的算法
• 考虑时间复杂度和空间复杂度
• 确保算法能正确处理所有测试用例

3. 实现要点

• 注意边界条件的处理
• 优化输入输出以提高效率
• 确保代码的正确性和鲁棒性

4. 调试和优化

• 使用测试用例验证算法正确性
• 分析性能瓶颈并进行优化
• 确保代码能通过所有测试点

注意事项

• 仔细处理数据类型和精度问题
• 注意数组越界和空指针问题
• 确保算法的时间复杂度符合要求

#include<cstdio>
using namespace std;
int T,n,m,k,p,I,i,j,u[210000],v[210000],w[210000],dis[110000],st[110000],wh[110000],inl[110000],top,*vmp[110000],*wmp[110000],a[5200000],*mp[5200000],num[5200000],ok[5200000],inw[5200000],ans,x,z[16000000],*qq;
void read(int &x)
{
	char c=getchar();
	while(c<'0'||c>'9')
	c=getchar();
	x=c-'0';
	while(1)
	{
		c=getchar();
		if(c<'0'||c>'9')
		return;
		x=x*10+c-'0';
	}
}
void _swap(int a,int b)
{
	int t=st[a];
	st[a]=st[b];
	st[b]=t;
	wh[st[a]]=a;
	wh[st[b]]=b;
}
void up(int x)
{
	while(x>1&&dis[st[x]]<dis[st[x>>1]])
	{
		_swap(x,x>>1);
		x=x>>1;
	}
}
void in(int x)
{
	top++;
	st[top]=x;
	wh[x]=top;
	up(top);
}
void down(int x)
{
	if(x<<1>top)
	return;
	if(x<<1==top)
	{
		if(dis[st[x]]>dis[st[x<<1]])
		_swap(x,x<<1);
		return;
	}
	if(dis[st[x]]>dis[st[x<<1]]||dis[st[x]]>dis[st[x<<1|1]])
	if(dis[st[x<<1]]<dis[st[x<<1|1]])
	{
		_swap(x,x<<1);
		down(x<<1);
	}
	else
	{
		_swap(x,x<<1|1);
		down(x<<1|1);
	}
}
int out()
{
	int ans=st[1];
	_swap(1,top);
	top--;
	down(1);
	return ans;
}
int getl(int x)
{
	int i,q;
	inl[x]=-2;
	for(i=1;i<=vmp[x][0];i++)
	if(wmp[x][i]==0)
	{
		if(inl[vmp[x][i]]==-2)
		{
			inl[x]=1;
			return 4;
		}
		if(inl[vmp[x][i]]==0)
		{
			q=getl(vmp[x][i]);
			if(q>0)
			{
				inl[x]=1;
				if(x!=q)
				return q;
				else
				return -1;
			}
		}
	}
	inl[x]=-1;
	return -1;
}
void get(register int x)
{
	register int i;
	ok[x]=1;
	for(i=1;i<=mp[x][0];i++)
	{
		a[mp[x][i]]=(a[mp[x][i]]+a[x])%p;
		ok[mp[x][i]]=1;
		num[mp[x][i]]--;
		if(num[mp[x][i]]==0)
		get(mp[x][i]);
	}
}
void dfs(register int x)
{
	register int i;
	inw[x]=1;
	for(i=1;i<=mp[x][0];i++)
	if(inw[mp[x][i]]==0)
	dfs(mp[x][i]);
}
main()
{
	read(T);
	for(I=1;I<=T;I++)
	{
		read(n);
		read(m);
		read(k);
		read(p);
		for(i=1;i<=m;i++)
		{
			read(u[i]);
			read(v[i]);
			read(w[i]);
			num[v[i]]++;
		}
		for(i=1;i<=n;i++)
		{
			vmp[i]=new int[num[i]+5];
			wmp[i]=new int[num[i]+5];
			vmp[i][0]=0;
			num[i]=0;
		}
		for(i=1;i<=m;i++)
		{
			vmp[v[i]][0]++;
			vmp[v[i]][vmp[v[i]][0]]=u[i];
			wmp[v[i]][vmp[v[i]][0]]=w[i];
		}
		for(i=1;i<n;i++)
		dis[i]=1000000000;
		dis[n]=0;
		for(i=1;i<=n;i++)
		if(inl[i]==0)
		getl(i);
		for(i=1;i<=n;i++)
		in(i);
		for(i=1;i<=n;i++)
		{
			x=out();
			for(j=1;j<=vmp[x][0];j++)
			if(dis[x]+wmp[x][j]<dis[vmp[x][j]])
			{
				dis[vmp[x][j]]=dis[x]+wmp[x][j];
				up(wh[vmp[x][j]]);
			}
		}
		if(dis[1]>=1000000000)
		{
			printf("0\n");
			for(i=1;i<=n;i++)
			{
				delete [] wmp[i];
				delete [] vmp[i];
				inl[i]=0;
			}
			continue;
		}
		if(inl[1]==1)
		{
			printf("-1\n");
			for(i=1;i<=n;i++)
			{
				delete [] wmp[i];
				delete [] vmp[i];
				inl[i]=0;
			}
			continue;
		}
		for(j=0;j<=k;j++)
		for(i=1;i<=m;i++)
		if(j+dis[v[i]]-dis[u[i]]+w[i]<=k)
		num[j*n+u[i]]++;
		qq=z;
		for(i=k*n+n;i>=1;i--)
		{
			mp[i]=qq;
			mp[i][0]=0;
			qq=qq+num[i]+1;
			num[i]=0;
		}
		for(j=0;j<=k;j++)
		for(i=1;i<=m;i++)
		if(j+dis[v[i]]-dis[u[i]]+w[i]<=k)
		{
			mp[j*n+u[i]][0]++;
			mp[j*n+u[i]][mp[j*n+u[i]][0]]=(j+dis[v[i]]-dis[u[i]]+w[i])*n+v[i];
		}
		a[1]=1;
		ok[1]=1;
		dfs(1);
		for(i=1;i<=k*n+n;i++)
		if(inw[i]==1)
		for(j=1;j<=mp[i][0];j++)
		num[mp[i][j]]++;
		get(1);
		for(i=1;i<=n;i++)
		if(inl[i]==1)
		{
			for(j=0;j<=k;j++)
			if(ok[j*n+i]==1)
			break;
			if(j<=k)
			break;
		}
		if(i<=n)
		printf("-1\n");
		else
		{
			ans=0;
			for(i=0;i<=k;i++)
			ans=(ans+a[i*n+n])%p;
			printf("%d\n",ans);
		}
		for(i=1;i<=n;i++)
		{
			delete [] wmp[i];
			delete [] vmp[i];
			inl[i]=0;
		}
		for(i=1;i<=k*n+n;i++)
		{
			a[i]=0;
			ok[i]=0;
			inw[i]=0;
			num[i]=0;
		}
	}
}