题解 P3953 【逛公园】

· · 题解

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

判断环的情况在代码中有提到

#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();  
}

安利一波博客吧。。(逃