题解「NOIP2017 逛公园」

有一个非常 ( ext{Naive}) 的想法,由于 (K) 很小,我们可以设 (f[x,i]) 为从 (x) 出发到 (n) ,长度不超过 (dis_x+i) 的路径条数,其中 (dis_x)(x o n) 的最短路长度。于是有转移方程:

[f[x,i]=sum f[y,(i+dis_x)-(dis_y+w(x,y))] ]

如果一个状态被访问超过 (1) 次,就说明存在 (0) 环,路径条数无限,直接输出 (-1) 即可。上述过程直接使用记忆化搜索实现,时间复杂度为 (O(nm))

#include<cstdio>
#include<queue>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<functional>
const int inf=0x3f3f3f3f;
int n,m,K,mod;
int cnt=0;
std::vector<int> mp[100005],val[100005];
int h[100005],to[400005],ver[400005],w[400005];
int dis[100005],b[100005],vis[100005][55],f[100005][55];
struct edge {int x,y,w;}e[200005];
inline int read() {
	register int x=0,f=1;register char s=getchar();
	while(s>'9'||s<'0') {if(s=='-') f=-1;s=getchar();}
	while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
	return x*f;
}
inline void add(int x,int y,int z) {to[++cnt]=y;ver[cnt]=h[x];w[cnt]=z;h[x]=cnt;}
inline void spfa() {
	std::queue<int> Q;
	for(register int i=1;i<=n;++i) b[i]=0,dis[i]=inf;
	dis[n]=0; Q.push(n);
	while(Q.size()) {
		int x=Q.front(); Q.pop(); b[x]=0;
		for(register int i=h[x];i;i=ver[i]) {
			int y=to[i];
			if(dis[y]>dis[x]+w[i]) {
				dis[y]=dis[x]+w[i];
				if(!b[y]) {b[y]=1; Q.push(y);}
			}
		} 
	}
}
inline int dfs(int x,int k) {
	if(vis[x][k]) {throw -1;}
	if(f[x][k]!=-1) return f[x][k];
	vis[x][k]=1; f[x][k]=(x==n); 
	for(register int i=0;i<mp[x].size();++i) {
		int y=mp[x][i],w=val[x][i];
		if(k+dis[x]-dis[y]-w>=0&&k+dis[x]-dis[y]-w<=K) f[x][k]=(f[x][k]+dfs(y,k+dis[x]-dis[y]-w))%mod;
	}
	vis[x][k]=0;
	return f[x][k];
}
int main() {
	int T=read();
	while(T--) {
		n=read(); m=read(); K=read(); mod=read();
		cnt=0; for(register int i=1;i<=n;++i) h[i]=0;
		for(register int i=1;i<=n;++i) {mp[i].clear();val[i].clear();}
		for(register int i=1;i<=m;++i) {
			int x=read(),y=read(),w=read();
			add(y,x,w); mp[x].push_back(y); val[x].push_back(w);
		}
		for(register int i=1;i<=n;++i) for(register int j=0;j<=K;++j) f[i][j]=-1,vis[i][j]=0;
		spfa(); 
		try {
			int res=dfs(1,K);
			printf("%d
",res);
		}catch(int x) {
			printf("-1
");
		} 
	}
	return 0;
} 
原文地址:https://www.cnblogs.com/tommy0103/p/14063909.html