当前位置: article > 正文

[AT ZONe2021]Sneaking_atcoder zone2021

作者：数据科学创新者 | 2024-02-01 08:43:38

踩

atcoder zone2021

Sneaking

题解

~~最短路板子~~

首先，我们可以考虑给它暴力建图来找最短路，但由于向上走的话，每个在它上面的点都可以被走到，所以我们的边数可能会达到 $n^4$ 级别，明显是不行的。

于是，我们得想一些方法来缩小它的边数。
从点 $i$ 向上走到点 $j$ 的花费是 $i - j + 1$ ，关键是这个 $+ 1$ 很难弄。
我们可以借鉴一些我们网络流分块的建图方法，~~虽然并不需要分块，~~ 对于每一个点建一个虚点，点 $i$ 到虚点 $i^{'}$ 的长度为 $1$ ，再从 $i^{'}$ 依次向 $(i - 1)^{'}$ 连一条为 $1$ 的边，最后再从 $i^{'}$ 向 $i$ 连一条为0的边。
其余的边，直接连就可以了。
这样，就可以边数达到 $n^2$ 的级别了，点数也是 $n^2$ 级别的。

然后，就是最短路。
当笔者兴致满满地打了一个spfa时，却被卡死了 ~~，这年头还有人卡SPFA的~~ 。
在这里插入图片描述
当然，换上堆优化的dij就可以过了。
Devil巨佬对spfa加上优化也过了。

时间复杂度 $O\left(n^2log\,n\right)$

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/52677