100722

首先考虑 $dp_{i,msk}$ 表示当前连通了 $msk$ 中所有关键点，并且当前连通的非关键点包含 $i$ 的最小代价。 然后考虑如何转移。我们先用 $Floyd$ 预处理所有点对之间的最短路 $dist_{i,j}$。同时，每次选取的两个用于合并的关键点集合一定没有交集，所以我们可以直接枚举 ......