CF20C 暴力题解(
houpingze
2021-06-29 16:01:09
大家好,我是hpz,我非常喜欢暴力,所以我就用暴力通过了此题。
这一题裸暴力`dfs`想都别想,所以必须大力优化,本篇题解主要就是讲优化。
1. 记忆化。
这是比较常见的优化。
我们在`dfs`函数中,一般需要有$\text{n}$(当前节点编号),和$\text{w}$(目前走过的路径权值),我们可以定义一个一维数组$\text{f}$,其中$f_{i}$表示走到节点$\text{i}$目前所需要花费的时间。
那么在`dfs`过程中,我们可以剪个枝,如果$f_n \leq w$就直接跳出。
2. 如果当前的$\text{w}$已经比我们的当前答案$\text{ans}$要大,直接跳出。
3. 玄学优化
这一点要实现得用$\text{vector}$存图。
我们在每条边存完以后,对于每一个点,从这个点出发的所有边按照**节点编号**排序。
至于为什么……就是防止CF的毒瘤Hacker给了一大堆边,但其实有$1-n$的边,而且就是最短路径的情况。
然后就可以通过了。
[code](https://www.luogu.com.cn/paste/akrypxop)