houpingze 的博客

膜拜zqs,sx,zlt,ymw,qyh官方博客

CF20C 暴力题解(

大家好,我是hpz,我非常喜欢暴力,所以我就用暴力通过了此题。

这一题裸暴力dfs想都别想,所以必须大力优化,本篇题解主要就是讲优化。

  1. 记忆化。

这是比较常见的优化。

我们在dfs函数中,一般需要有$\text{n}$(当前节点编号),和$\text{w}$(目前走过的路径权值),我们可以定义一个一维数组$\text{f}$,其中$f_{i}$表示走到节点$\text{i}$目前所需要花费的时间。

那么在dfs过程中,我们可以剪个枝,如果$f_n \leq w$就直接跳出。

  1. 如果当前的$\text{w}$已经比我们的当前答案$\text{ans}$要大,直接跳出。

  2. 玄学优化

这一点要实现得用$\text{vector}$存图。

我们在每条边存完以后,对于每一个点,从这个点出发的所有边按照节点编号排序。

至于为什么……就是防止CF的毒瘤Hacker给了一大堆边,但其实有$1-n$的边,而且就是最短路径的情况。

然后就可以通过了。

code


2021-06-29 16:01:09 in 题解