首页 > 编程札记 > 编程

NOIP2017 TG 逛公园动态规划/记忆化搜索

阅读：评论：0

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

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

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

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

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

如果有无穷多条合法的路线，请输出-1−1。

输入格式
第一行包含一个整数 TT, 代表数据组数。

接下来TT组数据，对于每组数据：第一行包含四个整数 N,M,K,PN,M,K,P，每两个整数之间用一个空格隔开。

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

输出格式
输出文件包含 TT 行，每行一个整数代表答案。

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

对于第一组数据，最短路为 33。 1 – 5, 1 – 2 – 4 – 5, 1 – 2 – 3 – 5 为 33 条合法路径。

【测试数据与约定】

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

测试点编号 T N M K 是否有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 是

解法：记忆化搜索

我们建两次图，正图用来跑SPFA，反图来进行动态规划，避免一些不必要的路径
设一个数组f[n][k]记录当前为n节点时，还剩k可走路径时的方案，然后枚举k，累加即可
跑好SPFA之后，每次挑出一条边来进行DP，取出最短路，看是否能放进去
如果我们已经搜索到当前状态，如果有搜索到当前状态，说明存在0环，那么我们就输出-1
多组数据，记得初始化

AC代码

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#define re register int
#define si 100010
using namespace std;
struct node {int to,len;
};
int T,n,m,k,p,d[si],f[si][55];
bool vis[si][55];
vector<node> hz[si];
vector<node> hf[si];
queue<int> q;
inline int read() {int x=0,cf=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') cf=-1;ch=getchar();}while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x*cf;
}
inline void spfa() {memset(d,0x3f,sizeof(d));q.push(1); d[1]=0;while(q.size()) {int x=q.front(); q.pop();for(re i=0;i<hz[x].size();i++) {int y=hz[x][i].to;if(d[y]>d[x]+hz[x][i].len) {d[y]=d[x]+hz[x][i].len;q.push(y);}}}
}
inline int dp(int root,int l) {int res=0;if(l<0||l>k) return 0;if(vis[root][l]) {vis[root][l]=false;return -1;}if(f[root][l]!=-1) return f[root][l];vis[root][l]=true;for(re i=0;i<hf[root].size();i++) {node e=hf[root][i];int val=,d[root]+]-e.len);if(val==-1) {vis[root][l]=false;return -1;}(res+=val)%=p;}vis[root][l]=false;if(root==1&&l==0) res++;f[root][l]=res; return res;
}
int main() {T=read();while(T--) {n=read(),m=read();k=read(),p=read();memset(f,-1,sizeof(f));for(re i=1;i<=n;i++) {hz[i].clear(),hf[i].clear();}for(re i=1;i<=m;i++) {int x=read(),y=read(),z=read();node e; e.to=y,e.len=z;hz[x].push_back(e); e.to=x;hf[y].push_back(e);}spfa();int ans=0,flag=0;for(re i=0;i<=k;i++) {int val=dp(n,i);if(val==-1) {printf("-1n");flag=1; break;}(ans+=val)%=p;}if(!flag) printf("%dn",ans);}return 0;
}