P3953 逛公园

问题描述

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

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

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

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

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

输入格式

第一行包含一个整数\(T\)，代表数据组数。

接下来\(T\)组数据，对于每组数据：

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

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

输出格式

输出文件包含\(T\)行，每行一个整数代表答案。

数据规模与约定

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

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

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

---

记忆化搜索真是太优雅了，除了需要判一下第0层过1点的边

正题：

其实基本应该都可以猜到正解的复杂度应该是\(O(NKT)\)的

有向图代表我们可以按一定的顺序进行\(DP\)

而边权又都是整数，妥妥的把多走的路\(k\)和节点压进状态转移方程

我们先不考虑0环

\(dp[i][j]\)代表在点\(j\)时多走\(i\)的路程的方案数。

为什么特意把\(i\)放在第一维？因为\(i\)相当于那个大的循环，把\(i\)做完了才做\(i+1\)

这和平常不建多层图的分层图（即在跑最短路的时候维护\(dis[i][j]\)数组，代表\(i\)节点\(j\)层的信息）做法并不一样，因为那种分层图可以直接按权值大小来或者多次松弛

转移方程:\(dp[i][v]=\sum dp[i+dis[v]-edge[u][v]-dis[u]][u]\)

当然，我们的记忆化搜索得倒着做

我们得把每一层的\(j\)都分别做一遍，这样，正环也是没有影响的

0环呢？

我们维护一个搜索树的栈，代表这个点和深度的二元组还在搜索树中，如果这个二元组在搜索树中的时候又被访问，则存在0环。

值得一提的是，这样在第0层时是有问题的，它判不出来过1点的0环，需要特判

---

Code：

#include <cstdio>

#include <cstring>

#include <queue>

#define P pair <int,int >

using namespace std;

const int N=100010;

int head[N],edge[N<<2],to[N<<2],Next[N<<2],cnt;

void add(int u,int v,int w)

{

    edge[++cnt]=w;to[cnt]=v;Next[cnt]=head[u];head[u]=cnt;

}

int read()

{

    int x=0;char c=getchar();

    while(c<'0'||c>'9') c=getchar();

    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}

    return x;

}

int n,m,k,p,t,dp[52][N],dis[N],used[N],vis[52][N],to0[N];

priority_queue <P,vector<P >,greater <P > > q;

P p0;

void disj()

{

    memset(dis,0x3f,sizeof(dis));

    memset(used,0,sizeof(used));

    dis[1]=0;

    p0.first=0,p0.second=1;

    q.push(p0);

    while(!q.empty())

    {

        int u=q.top().second;

        q.pop();

        if(used[u]) continue;

        used[u]=1;

        for(int i=head[u];i;i=Next[i])

        {

            if(i&1) continue;

            int v=to[i],w=edge[i];

            if(dis[v]>dis[u]+w)

            {

                dis[v]=dis[u]+w;

                p0.first=dis[v],p0.second=v;

                q.push(p0);

            }

        }

    }

}

void init()

{

    memset(head,0,sizeof(head));

    cnt=1;

    n=read(),m=read(),k=read(),p=read();

    int u,v,w;

    for(int i=1;i<=m;i++)

    {

        u=read(),v=read(),w=read();

        add(u,v,w),add(v,u,w);

    }

    disj();

    memset(dp,-1,sizeof(dp));

}

int flag=0;

void dfs0(int now)

{

    vis[0][now]=1;

    for(int i=head[now];i;i=Next[i])

        if((i&1)&&!edge[i])

        {

            if(vis[0][to[i]]) {flag=1;return;}

            dfs0(to[i]);

        }

    vis[0][now]=0;

}

int dfs(int now,int rest)

{

    if(vis[rest][now]) return -1;

    if(~dp[rest][now]) return dp[rest][now];

    vis[rest][now]=1;

    int v,w,res;

    for(int i=head[now];i;i=Next[i])

    {

        if(i&1)

        {

            v=to[i],w=edge[i];

            res=dis[now]+rest-dis[v]-w;

            if(res>=0)

            {

                if(dfs(v,res)==-1) return -1;

                (dp[rest][now]+=dfs(v,res))%=p;

            }

        }

    }

    vis[rest][now]=0;

    return ++dp[rest][now];

}

void work()

{

    memset(vis,0,sizeof(vis));

    int ans=0;

    dp[0][1]=1;dfs0(1);flag=0;

    if(flag) {printf("-1\n");return;}

    for(int i=0;i<=k;i++)

    {

        dp[i][n]=dfs(n,i);

        if(!(~dp[i][n])) {printf("-1\n");return;}

        (ans+=dp[i][n])%=p;

    }

    printf("%d\n",ans);

}

int main()

{

    t=read();

    while(t--)

    {

        init();

        work();

    }

    return 0;

}

---

2018.7.10