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，这一位可以省掉。