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


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

题解

作者：jzdx（hjh）

(最短路 + 记忆化搜索)

根据题意，我们需要找到所有从走到的长度为的路径个数

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

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

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

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

我们定义： 表示从走到的最短距离

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

计算我们可以反向建边以作为起点跑

对于数组

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

为边的长度

则从经过走到多走的距离为

解释 :表示当前从u选择走到的最短距离， 为u走到的最短距离

所以为这条路径对多余距离的贡献

所以

我们直接在原图中一遍搜索一遍进行状态计算，所以用到记忆化搜索
最终答案就是

无穷解的情况：

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

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

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

1. 如果是一个非零环

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

   所以
   状态只会被访问一次

2. 如果是一个零环

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

   所以

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

所以我们用表示是否被访问过，从往下递归前将,递归结束后将

如果在递归过程中则说明被遍历两次存在零环

时间复杂度

参考文献

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;
}

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

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目4月27日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴