CF20C 暴力题解（

大家好，我是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)