Noip2017逛公园(提高d1t3)

记忆化搜索

Posted by yjjr's blog on October 15, 2018

标签:SPFA,记忆化搜索

题目

题目传送门

题目描述

策策同学特别喜欢逛公园。公园可以看成一张个点条边构成的有向图,且没有 自环和重边。其中1号点是公园的入口,号点是公园的出口,每条边有一个非负权值, 代表策策经过这条边所要花的时间。

策策每天都会去逛公园,他总是从1号点进去,从号点出来。

策策喜欢新鲜的事物,它不希望有两天逛公园的路线完全一样,同时策策还是一个 特别热爱学习的好孩子,它不希望每天在逛公园这件事上花费太多的时间。如果1号点 到号点的最短路长为,那么策策只会喜欢长度不超过的路线。

策策同学想知道总共有多少条满足条件的路线,你能帮帮它吗?

为避免输出过大,答案对取模。

如果有无穷多条合法的路线,请输出

输入输出格式

输入格式

第一行包含一个整数 , 代表数据组数。

接下来组数据,对于每组数据: 第一行包含四个整数 ,每两个整数之间用一个空格隔开。

接下来行,每行三个整数,代表编号为的点之间有一条权值为 的有向边,每两个整数之间用一个空格隔开。

输出格式

输出文件包含 行,每行一个整数代表答案。

输入输出样例

输入样例#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

输出样例#1

3
-1

说明

【样例解释1】

对于第一组数据,最短路为 条合法路径。

【测试数据与约定】

对于不同的测试点,我们约定各种参数的规模不会超过如下

测试点编号                   是否有0边
1 5 5 10 0
2 5 1000 2000 0
3 5 1000 2000 50
4 5 1000 2000 50
5 5 1000 2000 50
6 5 1000 2000 50
7 5 100000 200000 0
8 3 100000 200000 50
9 3 100000 200000 50
10 3 100000 200000 50

对于 100%的数据,

数据保证:至少存在一条合法的路线。

分析

Attention:我的代码是假的,样例没法过,但能AC官方数据,挖坑待填!

表示到节点,还剩余的值可以去绕路的方案数

用SPFA处理最短路后

反向建图后记忆化搜索

假设在原图里有一条的边,那么可以绕路的冗余长度为

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 0x3f3f3f
using namespace std;
inline ll read(){
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
//**********head by yjjr**********
const int maxn=2e5+6;
int T,n,m,K,mod,cnt=0,last[maxn],x[maxn],y[maxn],z[maxn];
int que[maxn<<2],dis[maxn],inque[maxn],f[maxn][56],in[maxn],re[maxn],flag;
struct edge{int to,next,w;}e[maxn<<1];
void insert(int u,int v,int val){e[++cnt]=(edge){v,last[u],val};last[u]=cnt;}
inline int dfs(int x,int res){
#define v e[i].to
	if(~f[x][res])return f[x][res];
	f[x][res]=(x==1);
//	cout<<f[x][res]<<' '<<x<<' '<<res<<"R"<<endl;
	reg(x){
		int tmp=res-((dis[v]+e[i].w)-dis[x]);
//		cout<<tmp<<' '<<in[v]<<' '<<re[v]<<endl;
		if(tmp<0)continue;
		if(in[v]&&re[v]==tmp)flag=1;else in[v]=1,re[v]=tmp;
//		cout<<tmp<<' '<<in[v]<<' '<<re[v]<<endl;
		f[x][res]=(f[x][res]+dfs(v,tmp))%mod;
//		cout<<f[x][res]<<' '<<dfs(v,tmp)<<endl;
		in[v]=0,re[v]=0;
	}
	return f[x][res];
}
void work(){
	mem(last,0);cnt=0;mem(que,0);mem(inque,0);mem(dis,inf);
	n=read(),m=read(),K=read(),mod=read();
	rep(i,1,m){
		x[i]=read(),y[i]=read(),z[i]=read();
		insert(x[i],y[i],z[i]);
	}
	int head=0,tail=1;que[head]=1;dis[1]=0;inque[1]=1;
	while(head<tail){
		int now=que[head++];
		reg(now)
			if(dis[v]>dis[now]+e[i].w){
				dis[v]=dis[now]+e[i].w;
				if(!inque[v])inque[v]=1,que[tail++]=v;
			}
		inque[now]=0;
	}
	mem(last,0);cnt=0;mem(f,-1);flag=0;
	rep(i,1,m)insert(y[i],x[i],z[i]);
	int tmp=dfs(n,K);
	printf("%d\n",flag?-1:tmp);
}
int main()
{
	T=read();
	rep(i,1,T)work();
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr