代码

#include<bits/stdc++.h>
using namespace std;
long long int n,m,k,p,cnt=1,ans;
long long int dis[212345],to[212345],Next[212345],Last[212345],head[212345],len[212345];
long long int f[212345][51],back[212345],tail[212345];
bool vis[212345],ring[100001][51];
priority_queue<pair<int,int> > q;
void add(int u,int v,int w)
{
	len[cnt]=w;
	to[cnt]=v;back[cnt]=u;
	Next[cnt]=head[u];Last[cnt]=tail[v];
	head[u]=cnt;tail[v]=cnt;
	cnt++;
}
void dijkstra()
{
	dis[1]=0;
	q.push(make_pair(0,1));
	while(q.size())
	{
		int x=q.top().second;
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=head[x];i;i=Next[i])
		{
			int y=to[i],z=len[i];
			if(dis[y]>dis[x]+z)
			{
				dis[y]=dis[x]+z;
				q.push(make_pair(-dis[y],y));
			}
		}
	}
}
long long dfs(int now,int length)
{
	long long sum=0;
	if(length>k or length<0)
	{
		return 0;
	}
	if(ring[now][length])
	{
		ring[now][length]=0;
		return -1;
	}
	if(f[now][length]!=-1) return f[now][length];
	ring[now][length]=1;
	for(int i=tail[now];i;i=Last[i])
	{
		long long tmp=dfs(back[i],length+dis[now]-dis[back[i]]-len[i]);
		if(tmp==-1) 
		{
			ring[now][length]=0;
			return -1;
		}
		sum=(sum+tmp)%p;
	}
	ring[now][length]=0;
	if(now==1 and length==0) sum++;
	f[now][length]=sum;
	return sum;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		cnt=1;ans=0;
		memset(f,-1,sizeof(f));
		memset(Next,0,sizeof(Next));
		memset(Last,0,sizeof(Last));
		memset(ring,0,sizeof(ring));
		memset(head,0,sizeof(head));
		memset(tail,0,sizeof(tail));
		memset(dis,0x3f,sizeof(dis));
		memset(len,0,sizeof(len));
		memset(to,0,sizeof(to));
		memset(vis,0,sizeof(vis));
		cin>>n>>m>>k>>p;
		for(int i=1;i<=m;i++)
		{
			int u,v,w;
			cin>>u>>v>>w;
			add(u,v,w);
		}
		dijkstra();
		for(int i=0;i<=k;i++)
		{
			ans+=dfs(n,i);
		}
		if(ans>=0) cout<<ans%p<<endl;
		else cout<<-1<<endl;
	}
	return 0;
}

评测结果