做题记录整理图论/最短路/dp/记忆化搜索 P3953 [NOIP2017 提高组] 逛公园（2022/10/19）

P3953 [NOIP2017 提高组] 逛公园
https://122720.blog.luogu.org/p3953-ti-xie-ji-yi-hua-sou-suo

大佬讲得挺好的，我就不写了

#include<bits/stdc++.h>
#define for1(i,a,b) for(int i = a;i<=b;i++)
#define ll long long
#define mi(a,b) make_pair(a,b)
using namespace std;

struct node{
	int nex;
	int to;
	int w;
}a[500005],fan[500005];
int n,p,m,k;
int hd[500005],cnt;
int hd2[500005],cnt2;
bool kg; 	
int dp[500005][55];
void ru(int x,int y,int z)
{
	a[++cnt].to=y;
	a[cnt].w=z;
	a[cnt].nex=hd[x];
	hd[x]=cnt;
}
 void ru2(int x,int y,int z)
{
	fan[++cnt2].to=y;
	fan[cnt2].w=z;
	fan[cnt2].nex=hd2[x];
	hd2[x]=cnt2;
}
int dis[500005];
struct nn{
    int d,id;
    bool operator < ( const nn &A ) const{
	     return d>A.d; 
	 };
};
priority_queue<nn> dl;
 void dij(int s)
 {
        for1(i,1,n)
		    dis[i]=1e9;
        dis[s]=0; 
		dl.push((nn){0,s});
        while(!dl.empty())
		{
            nn now=dl.top(); 
			dl.pop();
            int val=now.d;
			int u=now.id;
            if(dis[u]<val) continue;
            for(int i=hd[u];i;i=a[i].nex)
			{
                int v=a[i].to;
                    if(dis[v]>dis[u]+a[i].w)
					{
                        dis[v]=dis[u]+a[i].w;
                        dl.push((nn){dis[v],v});
                    }
            }
        }
}
bool vis[500005][55];
int dfs(int now,int k)
{
	if(dp[now][k]!=-1) 
	    return dp[now][k];
	dp[now][k]=0,vis[now][k]=1;
	for(int i=hd2[now];i;i=fan[i].nex)
	{
		int v=fan[i].to;
		int x=dis[now]-dis[v]+k-fan[i].w;
		if(x<0) 
		    continue;
		if(vis[v][x]) 
		    kg=1;
		dp[now][k]=(dp[now][k]+dfs(v,x))%p;
	}
	vis[now][k]=0;
	return dp[now][k];
}


int main()
{
	int t;
	int u,v,w;
	cin>>t;
	while(t--)
	{
		cin>>n>>m>>k>>p;
		cnt=0;
		cnt2=0;
		kg=0;
		memset(hd,0,sizeof hd);
		memset(hd2,0,sizeof hd2);
        memset(dp,-1,sizeof dp);
        
		for1(i,1,m)
		{
			cin>>u>>v>>w;
			ru(u,v,w);
			ru2(v,u,w);
		}
		dij(1);
		for1(i,0,k)
		 dfs(n,i);
		if(kg) 
		{ 
		    printf("-1\n"); 
			continue; 
		}
		int ans=0;
        memset(dp,-1,sizeof dp); 
		dp[1][0]=1;
		for1(i,0,k)
			ans=(ans+dfs(n,i))%p;
		printf("%d\n",ans);
	}
	return 0;
}