洛谷P 3953[NOIP 2017]公園巡り

SPFA+DFS
まず、nから各点までの最短ルートを逆方向に構築して、kが特に小さいことを発見して、私たちは0からkまで毎回余分に歩くことができる長さを列挙することができて、それから1からdfsを始めて、それから記憶化して、記録はまだi番目の点まであって、まだjの長さの方案数を残して、それからこの状態を記録して今回の検索で木があって探したことがあって、探したことがあって環があります
そしてなくなった
コード#コード#

//By AcerMo
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int M=200500;
struct edge
{
	int to,cost;
}add;
int n,m,e,mod;
int dis[M],vis[M];
int jud[M/2][55],f[M/2][55],flag;
vectorv[M];
vectorg[M];
inline int read()
{
	int x=0;char ch=getchar();
	while (ch>'9'||ch='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;	
}
inline void SPFA()
{
	fill(dis,dis+n+1,2e9);
	queueq;dis[n]=0;q.push(n);
	while (q.size())
	{
		int u=q.front();q.pop();vis[u]=0;
		for (int i=0;idis[u]+pay)
			{
				dis[go]=dis[u]+pay;
				if (!vis[go])
					vis[go]=1,q.push(go);
			}
		}
	}
	return ;
}
inline int dfs(int x,int len)
{
	if (jud[x][len]) return flag=0,0;
	if (f[x][len]>0) return f[x][len];
	jud[x][len]=1;int ans=0;
	for (int i=0;i=0&&nl<=e) ans=(ans+dfs(go,nl))%mod;
		if (!flag) return 0;
	}
	jud[x][len]=0;
	if (x==n&&len==0) return f[x][len]=1;
	return f[x][len]=ans;
}
signed main()
{
	int t=read();
	while (t--)
	{
		n=read();m=read();e=read();mod=read();
		memset(f,-1,sizeof(f));memset(jud,0,sizeof(jud));
		for (int i=1;i<=m;i++)
		{
			int x=read(),y=read(),z=read();
			add.to=x;add.cost=z;v[y].push_back(add);
			add.to=y;add.cost=z;g[x].push_back(add);
		}
		SPFA();int ans=0;flag=1;
		for (int i=0;i<=e&&flag;i++)
		ans=(ans+dfs(1,i))%mod;
		flag?printf("%d
",ans):puts("-1");
		for (int i=1;i<=n;i++) v[i].clear(),g[i].clear();
	}
	return 0;	
}