洛谷3953 [NOIP2017]逛公园

题意

给出一个 $N$ 点 $M$ 边的有向图，令 $1\rightarrow N$ 的最短路长度为 $d$ ，求 $1\rightarrow N$ 的长度不超过 $d+k$ 的路径条数。

多组数据。 $N\le 100000$ ，$M\le 200000$ 。

题解

先跑一次反向最短路，记 $i\rightarrow n$ 的最短路长度为 $dis[i]$ 。

用 $d(i,j)$ 表示 $i\rightarrow j$ 的距离。令 $f[x][k]$ 表示 $d(x,n)\le dis[x]+k$ 时的方案数。那么对于所有的边 $(x,y,w)$ ，转移方程式为：

$$f[x][k] = \sum_y f[y][k-(dis[y]-dis[x]+w)]$$

可以通过记忆化搜索实现。

如果图中存在 $0$ 环，那么就会出现无穷多个方案，用一个 $in[x][k]$ 数组判环即可。

#include<bits/stdc++.h>
#define ll long long
#define pr pair<ll,ll>
#define mp make_pair

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    ll next,to,w;
} edge[200005],edge2[200005];
bool vis[100005],in[100005][55];
ll cnt,head[100005],cnt2,head2[100005],t,n,m,k,ha,a,b,c,dis[100005],f[100005][55];

inline void add(ll u,ll v,ll w)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    edge[cnt].w=w;
    head[u]=cnt;
}

inline void add2(ll u,ll v,ll w)
{
    edge2[++cnt2].to=v;
    edge2[cnt2].next=head2[u];
    edge2[cnt2].w=w;
    head2[u]=cnt2;
}

inline void dijkstra()
{
    priority_queue <pr,vector<pr>,greater<pr> > q;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    q.emplace(mp(dis[n]=0,n));
    while (!q.empty())
    {
        ll x=q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x]=1;
        for (ll i=head2[x];i;i=edge2[i].next)
        {
            ll y=edge2[i].to,w=edge2[i].w;
            if (dis[x]+w<dis[y])
            {
                dis[y]=dis[x]+w;
                q.emplace(mp(dis[y],y));
            }
        }
    }
}

ll dfs(ll x,ll k)
{
    if (in[x][k]) return -1;
    ll &ans=f[x][k];
    if (ans!=-1) return ans;
    ans=x==n;
    in[x][k]=1;
    for (ll i=head[x];i;i=edge[i].next)
    {
        ll y=edge[i].to,w=edge[i].w;
        ll nxtk=dis[y]-dis[x]+w,res;
        if (nxtk>k) continue;
        if ((res=dfs(y,k-nxtk))==-1) return -1;
        ans=(ans+res)%ha;
    }
    in[x][k]=0;
    return ans;
}

inline void init()
{
    cnt=cnt2=0;
    memset(head,0,sizeof(head));
    memset(head2,0,sizeof(head2));
}

signed main()
{
    t=read();
    while (t--)
    {
        init();
        n=read(); m=read(); k=read(); ha=read();
        for (ll i=1;i<=m;i++)
        {
            a=read(); b=read(); c=read();
            add(a,b,c);
            add2(b,a,c);
        }
        dijkstra();
        memset(f,-1,sizeof(f));
        memset(in,0,sizeof(in));
        printf("%lld\n",dfs(1,k));
    }
    return 0;
}