题解 P3953 【逛公园】
xzyxzy
2018-06-07 21:39:56
~~Noip炸~,于是我到现在才开始更正题目。。~~
# 记忆化搜索做法
这种题目一点也不套路,很不好做,甚至我看了一个小时题解才弄懂
那么首先看K很小,所以可以把K纳入状态中
令dp[i][j]表示到i号节点,还有j的值可以去绕弯路的方案数(不一定j要绕完,可以绕0~j之间的弯路)
那么答案就是dp[N][K]
### 全程序分为三个部分
#### 一、读入
略
#### 二、预处理每个点到1的最短路
略
#### 三、反向建图后记搜答案
假设在原图中有一条x->y,w的边
那么从x走到y就是dis[x]+w
实际上最短路是dis[y]
那么绕弯路的长度是 (dis[x]+w)-dis[y]
所以DFS(x,res)表示到达x点还剩res步可以绕的方案数
$$ dp[x][res]=\sum_{y,y->x}dp[y][res-(dis[x]+w-dis[y])] $$
边界条件是到达1返回1
判断环的情况在代码中有提到
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
using namespace std;
int read()
{
char ch=getchar();int h=0,t=1;
while((ch>'9'||ch<'0')&&ch!='-') ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') h=h*10+ch-'0',ch=getchar();
return h*t;
}
const int MAXN=210000;
int T,N,M,K,mod,cnt,head[MAXN];
int fr[MAXN],to[MAXN],w[MAXN];
int dis[MAXN],vis[MAXN],dp[MAXN][51];
int in[MAXN],re[MAXN],flag;
queue<int> Q;
struct edge{int next,to,w;}a[MAXN<<1];
void link(int x,int y,int w)
{
a[++cnt]=(edge){head[x],y,w};
head[x]=cnt;
}
int DFS(int x,int res)//返回到达x点还剩res步可以绕的方案数
{
if(~dp[x][res]) return dp[x][res];
dp[x][res]=(x==1);
for(int i=head[x];i;i=a[i].next)
{
int R=a[i].to;
int tt=res-((dis[R]+a[i].w)-dis[x]);//通过这条边多绕了一会
if(tt<0) continue;
if(in[R]&&re[R]==tt) flag=1;//如果说res一直没有减少的情况下搜出来一个圈,说明有0环
else in[R]=1,re[R]=tt;
(dp[x][res]+=DFS(R,tt))%=mod;
in[R]=0;re[R]=0;
}
return dp[x][res];
}
void Work()
{
//Part 1 初始化/读入
memset(head,0,sizeof(head));cnt=0;
N=read();M=read();K=read();mod=read();
for(int i=1;i<=M;i++)
{
fr[i]=read();to[i]=read();w[i]=read();
link(fr[i],to[i],w[i]);
}
//Part 2 SPFA预处理距离
memset(dis,63,sizeof(dis));
Q.push(1);dis[1]=0;vis[1]=1;
while(!Q.empty())
{
int x=Q.front();
for(int i=head[x];i;i=a[i].next)
{
int R=a[i].to;
if(dis[R]<=dis[x]+a[i].w) continue;
dis[R]=dis[x]+a[i].w;
if(!vis[R]) vis[R]=1,Q.push(R);
}
Q.pop();vis[x]=0;
}
//Part 3 建反图DFS记搜
memset(head,0,sizeof(head));cnt=0;
memset(dp,-1,sizeof(dp));flag=0;
for(int i=1;i<=M;i++)
link(to[i],fr[i],w[i]);
DFS(N,K);
printf("%d\n",flag?-1:DFS(N,K));
}
int main()
{
T=read();while(T--)Work();
}
```
~~安利一波[博客](https://www.cnblogs.com/xzyxzy/)吧。。(逃~~