P3959 [NOIP2017 提高组] 宝藏 题解
一道状压 DP 题。
发现这道题 \(n \leq 12\) 其实特别小，因此可以考虑状压，而且可以直接邻接矩阵存图。
首先我们发现这道题打通的路径构成的图一定是棵树，而根节点就是起点，因此我们需要知道每一个点距离根节点的距离，也就是深度 \(dep\)，根节点深度为 0。
设 \(f_{i,j,d}\) 表示当前被挖到的最新的点是 \(i\)，已经连通的点的点集为 \(j\)（状压为 \(2^{12}-1\)），目前已经挖了 \(d\) 个点的最小花费。
于是我们有以下转移方程：
\[f_{v,j,d+1}=\min\{f_{u,j|(1<<(v-1)),d}+(dep_u+1) \times e_{u,v}|u \to v\} \]其中 \(e_{u,v}\) 是 \((u,v)\) 的边权。
上述转移方程的意义就是我们从所有可达的未选取的点中选取一个，然后进行转移。
发现这个转移方程写成 DFS 的方式会更加合适，因为 DFS 除了可以进行转移以外还可以处理 \(dep\) 数组，于是我采用记忆化搜索实现。
Code：GitHub CodeBase-of-Plozia P3959 [NOIP2017 提高组] 宝藏.cpp