刷题记录:牛客NC16416逛公园

传送门:牛客

题目描述:

策策同学特别喜欢逛公园。 公园可以看成一张 N 个点 M 条边构成的有向图，且没有自环和重边。其中 1 号点是公园的入口， N 号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。
策策每天都会去逛公园，他总是从 1 号点进去，从 N 号点出来。
策策喜欢新鲜的事物，他不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，他不希望每天在逛公园这件事上花费太多的时间。如果 1 号点到 N 号点的最短路长为 d，那么策策只会喜欢长度不超过 d + K 的路线。
策策同学想知道总共有多少条满足条件的路线，你能帮帮他吗？
为避免输出过大，答案对 P 取模。
如果有无穷多条合法的路线，请输出 −1。
输入:
2
5 7 2 10
1 2 1
2 4 0
4 5 2
2 3 2
3 4 1
3 5 2
1 5 3
2 2 0 10
1 2 0
2 1 0
输出:
3
-1

一道思维难度比较高的最短路+dp的题目

主要思路:

1. 首先我们看到这道题不难想到最短路.然后我们看一下我们的题目,题目中要求我们算出有多少种不同的路线,对于这种计算路线数量的问题,我们不难想到可以使用dp来解决,那么我们的dp方程应该如何设计呢
2. 我们首先会想到,我们可以使用$dp[v][i]$来记录从$v$节点出发到$n$点需要$i$点花费的数量.那么对于我们的$v$节点的上一个邻接点$u$来说,我们的$v$节点给$u$做出的贡献就是$i+edge[u][v].w$,此时我们不难就可以求出$dp[u][i+edge[u][v].w]$了.对于这种dp,我们可以使使用类似于树形dp的$dfs$来解决,跟树形dp不同的是因为我们此时是一张图需要使用记忆化来优化
3. 但是我们上述的dp方程是不行的,因为我们会发现我们的$i$非常大,所以我们的数组会开不下,所以我们需要进行一点优化.我们会发现$k$非常小,这就很好,这意味着我们可以根据我们的k来进行优化.我们可以将我们的$dp[v][i]$改为从$v$节点出发到$n$点需要花费比最短路$dis[i]$多走了$i$点多余距离的路径的个数.那么对于我们的$u$节点来说,我们假设选择了$v$节点的话,我们多走的距离就是$dis[v]+edge[u][v].w-dis[u]$距离,那么我们同样可以进行转移$dp[u][i]=f[v][i-(edge[u][v].w+dis[v]-dis[u])]$
4. 搞清楚上面的dp方程之后,我们还需要解决一个重要的事情,就是无穷多合法路线的情况.因为我们的边权是大于等于0的,所以假设我们有无穷多合法路线,这就意味着我们走的路线存在一个0环,为什么是0环呢.因为对于0环来说,我们可以在这个环中绕了随意圈数都没有任何关系.此时就贡献除了多个方案.并且对于我们的0环来说,也就是在从u出发又回到了u并且此时的花费一样,我们可以使用$vis$数组来记录就行

注意,因为我们的边权可以为0,所以我们的dp数组初始化应该为-1

注意各数组的初始化问题

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define int long long
#define maxn 101000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Node{
	int v,w;
};
vector<Node>edge[maxn],edge2[maxn];
struct heapnode{
	int u,d;
	bool operator<(const heapnode &rhs) const {
		return d>rhs.d;
	}
};
int n,m,k,p;
int vis[maxn],dis[maxn];
void Dij(int S) {
	priority_queue<heapnode>q;
	for(int i=1;i<=n;i++) dis[i]=int_INF;
	dis[S]=0;
	q.push({S,0});
	while(!q.empty()) {
		heapnode f=q.top();q.pop();
		int u=f.u;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=0;i<edge2[u].size();i++) {
			int v=edge2[u][i].v;
			if(dis[v]>dis[u]+edge2[u][i].w) {
				dis[v]=dis[u]+edge2[u][i].w;
				q.push({v,dis[v]});
			}
		}
	}
}
int flag=0;int dp[maxn][60];int vis2[maxn][60];
int dfs(int u,int leftover) {
	if(vis2[u][leftover]) {
		flag=1;return 0;
	}
	vis2[u][leftover]=1;
	if(dp[u][leftover]!=-1) return dp[u][leftover];
	dp[u][leftover]=0;
	for(int i=0;i<edge[u].size();i++) {
		int v=edge[u][i].v;
		int t=dis[v]+edge[u][i].w-dis[u];
		if(leftover-t<0) continue;
		dfs(v,leftover-t);
		vis2[v][leftover-t]=0;
		dp[u][leftover]=(dp[u][leftover]+dp[v][leftover-t])%p;
		if(flag) return 0;
	}
	if(u==n&&leftover==0) dp[u][leftover]=1;
	return dp[u][leftover];
}
void init() {
	flag=0;
	for(int i=1;i<=n;i++) {
		edge[i].clear();edge2[i].clear();
	}
	for(int i=1;i<=n;i++) {
		vis[i]=0;
	}
	for(int i=1;i<=n;i++) {
		for(int j=0;j<=k;j++) {
			dp[i][j]=-1;vis2[i][j]=0;
		}
	}
}
int T;
signed main() {
	T=read();
	while(T--) {
		n=read();m=read();k=read();p=read();
		init();
		for(int i=1;i<=m;i++) {
			int u=read(),v=read(),w=read();
			edge[u].push_back({v,w});
			edge2[v].push_back({u,w});
		}
		Dij(n);
		int ans=0;
		for(int i=0;i<=k;i++) {
			ans=(ans+dfs(1,i))%p;
			if(flag==1) {
				break;
			} 
			vis2[1][i]=0;//注意这一步,这个和dfs里面的清0步骤位置有关
		}
		if(flag==1) printf("-1\n");
		else printf("%lld\n",ans);
	}
}