洛谷 P3953 NOIp2017提高组 逛公园 题解【记忆化搜索】【最短路】

作者: wjyyy 分类: DP,搜索,最短路,最短路计数,解题报告,记忆化搜索 发布时间: 2018-07-10 17:07

点击量:28

 

   我要是考场上会什么最短路……

 

【问题描述】

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

 

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

 

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

 

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

 

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

 

【输入格式】

输入文件名为 park.in。

 

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

 

接下来T组数据,对于每组数据:

 

第一行包含四个整数N,M,K,P每两个整数之间用一个空格隔开。

 

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

 

【输出格式】

输出文件名为 park.out。

 

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

 

【输入输出样例 1】

park.in 
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

 

park.out
3

-1

对于第一组数据,最短路为3。

 

1–5, 1–2–4–5,1–2–3–5为3条合法路径。

 

【数据规模与约定】

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

 

对于 100%的数据, \(1\le P \le 10^9,1\le a_i,b_i \le N, 0\le c_i \le 1000\)。

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

 

前言:

   简析一下数据梯度。

 

   10分:floyd求最短路计数。

 

   30分:spfa求最短路计数。

 

   70分:不用判0环(输出-1)的正解。

 

   100分:正解/没有判过1的0环(样例2没过)\(\Rightarrow \)

 

题解:

   可以用记忆化搜索过掉,首先SPFA预处理出从1出发的单源最短路径,接着判断有无过1的0环(出于严谨,虽然没有必要),有则输出-1。考虑类似背包的转移,也就是对于点\(v,d[v]+x,x\in [0,k]\),设存在边\((u,v)=w\),则可以由\(t=x-[w-(dis[v]-dis[u])]\)转移。当w在最短路上时,就是由同层的\(x\)转移,如果不在最短路上,就是由不同层的\(t\)转移。当\(t\le 0\)时,不合法,就不转移。

 

   因为我们的状态是由前面(靠近源点)状态转移过来的,所以记忆化搜索是倒着做的。在做完SPFA后,将图的方向反过来,就是dfs时用的图。那么一个点如果被搜索过,可以直接调用它的状态;如果一个点没有搜索过,就继续搜索它;如果它还在系统栈里,说明找到了环,此时判断上述\(t\)是否合法,如果不合法则递归,如果合法就当它没有搜索过。如果出现0环,则两次找到某个点时,利用的\(x\)是相同的,此时判断找到0环,输出-1。

 

   同时,记忆化搜索是要做\(k\)遍的,因为做第i次时,只有f[u][1…i]是全部有效/合法的。所以做k次保证了所有转移来的都是合法的,不合法的初始值f[i][j]=-1,f[1][0]=1,存的是方案数。

 

Code:

#include<cstdio>
#include<cstring>
#include<queue>
using std::deque;
struct edge
{
    int n,v,nxt;
    edge(int n,int v,int nxt)
    {
        this->n=n;
        this->v=v;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[210000],E[210000];
int head[101000],Head[101000],Ecnt=-1,ecnt=-1;
void add(int from,int to,int v)
{
    e[++ecnt]=edge(to,v,head[from]);
    head[from]=ecnt;
}
void Add(int from,int to,int v)
{
    E[++Ecnt]=edge(to,v,Head[from]);
    Head[from]=Ecnt;
}
int p;
int f[101000][55];
bool in[101000];
int dis[101000];
void spfa()
{
    memset(dis,0x3f,sizeof(dis));
    in[1]=true;
    dis[1]=0;
    deque<int> q;
    q.push_back(1);
    while(!q.empty())
    {
        int k=q.front();
        q.pop_front();
        in[k]=false;
        for(int i=Head[k];~i;i=E[i].nxt)
        {
            if(dis[E[i].n]>dis[k]+E[i].v)
            {
                dis[E[i].n]=dis[k]+E[i].v;
                if(!in[E[i].n])
                {
                    in[E[i].n]=true;
                    if(q.empty()||dis[E[i].n]<dis[q.front()])
                        q.push_front(E[i].n);
                    else
                        q.push_back(E[i].n);
                }
            }
        }
    }
}

bool used[101000][51];
int flag=0;
int dfs(int x,int k)
{
    int t;
    if(f[x][k]==-1)
        f[x][k]++;
    for(int i=head[x];~i;i=e[i].nxt)
    {
        int tmp=0;
        t=k-(e[i].v-(dis[x]-dis[e[i].n]));
        if(t<0)
            continue;
        if(!used[e[i].n][t]&&~f[e[i].n][t])
            f[x][k]+=f[e[i].n][t];
        else
        {
            if(used[e[i].n][t])
            {
                flag=1;
                return 0;
            }
            used[e[i].n][t]=true;
            f[x][k]+=dfs(e[i].n,t);
            if(!tmp)
                used[e[i].n][t]=false;
            if(flag)
                return 0;
        }
        f[x][k]%=p;
    }
    return f[x][k];
}
bool Used[101000];
int nega;
void Dfs(int x)//判过1的0环
{
    for(int i=Head[x];~i;i=E[i].nxt)
        if(E[i].v==0)
        {
            if(Used[E[i].n])
            {
                nega=1;
                return;
            }
            Used[E[i].n]=true;
            Dfs(E[i].n);
        }
}

int main()
{
    int T,n,m,k;
    int u,v,w;
    scanf("%d",&T);
    while(T--)
    {
        memset(Used,0,sizeof(Used));
        memset(used,0,sizeof(used));
        memset(in,0,sizeof(in));
        memset(f,-1,sizeof(f));
        scanf("%d%d%d%d",&n,&m,&k,&p);
        memset(head,-1,sizeof(head));
        memset(Head,-1,sizeof(Head));
        ecnt=-1;
        Ecnt=-1;
        for(int i=1;i<=m;++i)
        {
            scanf("%d%d%d",&u,&v,&w);
            Add(u,v,w);
            add(v,u,w);
        }
        spfa();
        Used[1]=true;
        nega=0;
        Dfs(1);

        if(nega)
        {
            puts("-1");
            continue;
        }
            
        f[1][0]=1;
        int ans=0;
        for(int i=0;i<=k;++i)
        {
            memset(used,0,sizeof(used));
            used[n][i]=true;
            flag=0;
            f[n][i]=dfs(n,i)%p;
            ans+=f[n][i];//答案是全部d+x x∈[0,k]的所有合法方案
            ans%=p;
            if(flag)
            {
                ans=-1;
                break;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */