RainAir
My OI Blog
RainAir
「NOIP2017」逛公园

题意描述

给定一张无向图,定义 $ S $ 为 $ 1 $ 到 $ N $ 的最短路,求该无向图 $ 1 $ 到 $ N $ 的路径中长度小于等于 $ S+K $ 的方案。

题目链接

推荐大家去 uoj 多交一些题目,上面有很多 hack 数据。(像我之前认为 dij 就是 spfa+priority_queue)。

解题报告

这一题我们首先一定要跑一遍从 $n$ 到 $1$ 的最短路,记录下 $n$ 到 $i$ 的最短路径长度 $dis_i$

我们考虑动态规划。最长为 $N+k$ 可以理解为你可以多跑长度 $k$。

这样我们写一个 dfs 来搜索,然后无脑记忆化一下。

设 $f[v][i]$ 表示到第 $v$ 个点,走目前的路+之后走最短路到达终点的花费大于最短路不超过 $k$ 的路径条数。

深搜到每一个点的时候如果这一个点是 $n$ 就当前状态记录的答案 $ +1$。枚举这个点指向的点 $next$ 和出边 $w$,转移有 $f[v][i] \to f[next][dis_{next}+w-dis_v]​$ 。

为什么从 $n$ 跑到 $1$ 的原因就是避免掉那些走不到终点的点也加入状态。

然后判断无限多解。只需要一个状态在同一条路径中出现了两次就有无限多种解了。

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/90
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「NOIP2017」逛公园
题意描述 给定一张无向图,定义 $ S $ 为 $ 1 $ 到 $ N $ 的最短路,求该无向图 $ 1 $ 到 $ N $ 的路径中长度小于等于 $ S+K $ 的方案。 题目链接 推荐大家去 uoj 多交一些题目,上面…
扫描二维码继续阅读
2018-08-03
标签
近期评论