2021-04-22 11:53 已编辑辽宁工业大学 C++

关注

【每日一题】2021年4月21日题目精讲

题号 NC16416
名称逛公园
来源 NOIP2017提高组复赛
 每日一题三期汇总贴~

如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者：jzdx（hjh）

(最短路 + 记忆化搜索)

根据题意，我们需要找到所有从 $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;
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！