【每日一题】2021年4月21日题目逛公园

题号 NC16416
名称逛公园
来源 NOIP2017提高组复赛

时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

策策同学特别喜欢逛公园。公园可以看成一张 N 个点 M 条边构成的有向图，且没有自环和重边。其中 1 号点是公园的入口， N 号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。
策策每天都会去逛公园，他总是从 1 号点进去，从 N 号点出来。
策策喜欢新鲜的事物，他不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，他不希望每天在逛公园这件事上花费太多的时间。如果 1 号点到 N 号点的最短路长为 d，那么策策只会喜欢长度不超过 d + K 的路线。
策策同学想知道总共有多少条满足条件的路线，你能帮帮他吗？
为避免输出过大，答案对 P 取模。
如果有无穷多条合法的路线，请输出 −1。

样例

对于第一组数据，最短路为 3。
1 - 5, 1 - 2 - 4 - 5, 1 - 2 - 3 - 5 为 3 条合法路径。

对于所有数据 0 <= T <= 5 ,5 <= N <= 100000,1 <= M <= 200000 , k <= 50,存在0边

算法

(最短路 + 记忆化搜索)

根据题意，我们需要找到所有从 $1$ 走到 $n$ 的长度为 $[d,d +k]$ 的路径个数

对于这种最短路上的路径的计数问题我们一般想到的都是用动态规划

首先我们先思考一下状态表示：

首先对于一张有向图来说从每一个点走到 $n$ 的最短路长度是唯一的，而变的是 $k$ 的大小

我们发现 $k$ 的大小最多只有 $50$ ，所以我们可以如下定义状态表示

我们定义 $dist[i]$ 表示从 $i$ 走到 $n$ 的最短距离

$f[i][j]表示当前从点i走到点n比dist[i]多走了j点多余距离的路径的个数$

接着我们考虑一下数组的计算：

计算 $dist[i]$ 我们可以反向建边以 $n$ 作为起点跑 $dijkstra$

对于数组 $f[i][j]$

我们考虑图中的某一条从 $u$ 走到 $n$ 的路径对多余距离的贡献

$w[u][v]$ 为边 $<u,v>$ 的长度

则从 $u$ 经过 $<u,v>$ 走到 $n$ 多走的距离为 $w[u][v] + dist[v] - dist[u]$

解释 : $w[u][v] + dist[v]$ 表示当前从u选择 $<u,v>$ 走到 $n$ 的最短距离， $dist[u]$ 为u走到 $n$ 的最短距离

所以 $w[u][v] + dist[v] - dist[u]$ 为这条路径对多余距离的贡献

所以 $f[u][j] = f[v][j - (w[u][v] + dist[v] - dist[u])]$ $(j >= w[u][v] + dist[v] - dist[u])$

我们直接在原图中一遍搜索一遍进行状态计算，所以用到记忆化搜索
最终答案就是 $\sum_{i=0}^{k}dfs[1][i]$

无穷解的情况：

如果图中存在零环我们可以在环中转若干圈后再走最短路到达 $n$ 点，从而得到不同的路径

于是我们的可以得到无数条合法路径

我们首先考虑一下如果存在环状态会如何转移

如果是一个非零环

进入这个环之前多走距离是 $ow$ ，那么经过这个环之后多走的距离就变成了了 $ow'$ 由于是非零环且所有边都是非负数

所以 $ow \ != ow'$
状态 $state(u,ow)$ 只会被访问一次
如果是一个零环

进入这个环之前多走距离是 $ow$ ，那么经过这个环之后多走的距离就变成了了 $ow'$ 由于是零环

所以 $ow \ == ow'$

$state(u,ow)$ 这个状态被同时经过了两次（自身可以更新自身的数据说明存在零环）可以利用这个来判断是否出现零环

所以我们用 $vis[i][j]$ 表示 $state(i,j)$ 是否被访问过，从 $state(i,j)$ 往下递归前将 $vis[i][j] = true$ ,递归结束后将 $vis[i][j] = false$

如果在递归过程中 $vis[i][j] == true$ 则说明 $state(i,j)$ 被遍历两次存在零环

时间复杂度 $O(MlogN + (N + M)K)$

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 100010,M = 200010,INF = 0x3f3f3f3f;
int h[N],h1[N],ne[M * 2],e[M * 2],w[M * 2],idx;
int dist[N];
LL f[N][55];
bool vis[N][55];
bool st[N];
bool flag;
int n,m,k,p;

void add(int h[],int a,int b,int c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}

void dijkstra()
{
    priority_queue<PII,vector<PII>,greater<PII>> q;
    for(int i = 1;i <= n;i ++) dist[i] = INF;
    dist[n] = 0;
    q.push(make_pair(0,n));
    while(q.size())
    {
        PII t = q.top();
        q.pop();
        int ver = t.second,distance = t.first;
        if(st[ver]) continue;
        st[ver] = true;
        for(int i = h1[ver];~i;i = ne[i])
        {
            int j = e[i];
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                q.push(make_pair(dist[j],j));
            }
        }
    }
}

LL dfs(int u,int o)
{
    if(vis[u][o])
    {
        flag = true;
        return 0;
    }
    vis[u][o] = true;
    LL &v = f[u][o];
    if(v != -1)
    {
        vis[u][o] = false;
        return v;
    }
    v = 0;
    for(int i = h[u];~i;i = ne[i])
    {
        int j = e[i];
        int t = o - (dist[j] + w[i] - dist[u]);
        if(t >= 0) v = (v + dfs(j,t)) % p;
        if(flag) return 0;
    }
    vis[u][o] = false;
    if(u == n && o == 0) v = 1;
    return v;
}

void solve()
{
    scanf("%d%d%d%d",&n,&m,&k,&p);
    for(int i = 1;i <= n;i ++)
    {
        h[i] = h1[i] = -1;
        st[i] = false;
        for(int j = 0;j <= k;j ++)
        {
            f[i][j] = -1;
            vis[i][j] = false;
        }
    }
    idx = 0;
    flag = 0;
    while(m --)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(h,a,b,c);
        add(h1,b,a,c);
    }
    dijkstra();
    LL res = 0;
    for(int i = 0;i <= k;i ++)
    {
        res = (res + dfs(1,i)) % p;
        if(flag) break;
    }
    if(flag) puts("-1");
    else printf("%lld\n",res);
}

int main()
{
    int T = 1;
    scanf("%d",&T);
    while(T --)
    {
        solve();
    }
    return 0;
}

【每日一题】2021年4月21日题目 逛公园