p3451 sol（POI2007 ATR）

注意到 $k$ 很小，可以状压直接维护，故考虑状压 dp。先将点转化为 0-index。

设计状态 $f_{S,i}$ 表示已经停留于 $S$ 状态中的点，当前在 $i$ 节点的最短路。

预处理出 $dis_{i,j}(i\in[1,k]\cup\{n-1\},j\in[0,n-1])$ 表示 $i$ 到 $j$ 的距离。转移利用 $dis$ 推推式子就行了。

考虑空间优化。注意到 $S$ 的第 $i$ 位由于确定它被停留了，所以一定为 $1$，这一位可以省掉。