洛谷 P3953 逛公园【spfa+记忆化dfs+bfs】

spfa预处理出最短路数组dis，然后反向建边bfs出ok[u]表示u能到n点

然后发现有0环的话时候有inf解的，先dfs找0环判断即可

然后dfs，设状态f[u][v]为到u点，还可以跑最短路+v的长度，记忆化，然后直接搜即可

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<vector>

using namespace std;

const int N=100005,inf=1e9;

int T,n,m,k,mod,h[N],cnt,ans[N][55],dis[N],len,v[N],ti,fl;

bool f[N][55],ok[N];

vector<int>a[N];

struct qwe

{

	int ne,to,va;

}e[N<<1];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

inline void jia(int &x,int y)

{

	x+=y;

	if(x>=mod)

		x-=mod;

}

void add(int u,int v,int w)

{

	cnt++;

	e[cnt].ne=h[u];

	e[cnt].to=v;

	e[cnt].va=w;

	h[u]=cnt;

}

void zer(int u)

{

	v[u]=ti;

	for(int i=h[u];i;i=e[i].ne)

		if(e[i].va==0)

		{

			if(v[e[i].to]==ti)

			{

				fl=1;

				return;

			}

			else if(!v[e[i].to])

				zer(e[i].to);

		}

}

int dfs(int u,int v)

{

	if(v<0)

		return 0;

	if(f[u][v])

		return ans[u][v];

	int sm=(u==n);

	for(int i=h[u];i;i=e[i].ne)

		if(ok[e[i].to])

			sm=(sm+dfs(e[i].to,v-(e[i].va-(dis[e[i].to]-dis[u]))))%mod;

	f[u][v]=1,ans[u][v]=sm;

	return sm;

}

int main()

{

	T=read();

	while(T--)

	{

		memset(h,0,sizeof(h));

		memset(ok,0,sizeof(ok));

		memset(f,0,sizeof(f));

		memset(ans,-1,sizeof(ans));

		cnt=0;ti=0,fl=0;

		n=read(),m=read(),k=read(),mod=read();

		for(int i=1;i<=n;i++)

			a[i].clear();

		for(int i=1;i<=m;i++)

		{

			int x=read(),y=read(),z=read();

			add(x,y,z);

			a[y].push_back(x);

		}

		for(int i=1;i<=n&&!fl;i++)

			if(!v[i])

				ti++,zer(i);

		if(fl)

		{

			puts("-1");

			continue;

		}

		queue<int>q;

		ok[n]=1,q.push(n);

		while(!q.empty())

		{

			int u=q.front();

			q.pop();

			for(int i=0;i<a[u].size();i++)

				if(!ok[a[u][i]])

				{

					ok[a[u][i]]=1;

					q.push(a[u][i]);

				}

		}

		for(int i=1;i<=n;i++)

			dis[i]=inf,v[i]=0;

		dis[1]=0,v[1]=1;

		q.push(1);

		while(!q.empty())

		{

			int u=q.front();

			q.pop();

			v[u]=0;

			for(int i=h[u];i;i=e[i].ne)

				if(dis[e[i].to]>dis[u]+e[i].va)

				{

					dis[e[i].to]=dis[u]+e[i].va;

					if(!v[e[i].to])

					{

						v[e[i].to]=1;

						q.push(e[i].to);

					}

				}

		}

		// for(int i=1;i<=n;i++)

			// cerr<<ok[i]<<endl;

		printf("%d\n",dfs(1,k));

	}

	return 0;

}