题意

坐标系中给定一个包的位置 \(x_0,y_0\)，有 \(n\) 个物品给定坐标 \(x_i,y_i\)。从一个点到另一个点的时间花费为两点间欧几里得距离的平方。你从包出发，每次最多拿 \(2\) 个物品，求把所有物品放到包里的最小耗时。

• \(1\le n\le24,1\le x_i,y_i\le 100\),\(i\in[0,n]\)。

---

思路

看见数据范围立刻想到状压 dp。

考虑设 \(dp_{statu}\) 表示当前拿取物品的状态为 \(statu\) 时的最小耗时，其中 \(statu\) 的第 \(i\) 位为 \(0(1)\) 表示第 \(i\) 个物品没放到包里(放到包里)。

肉眼可见最终答案为 \(dp_{(11\cdots1)_2}\) 即 \(dp_{2^n-1}\)

---

考虑如何转移。

显然有 \(dp_0=0\)，表示没开始拿不耗时。

其余的初始化为 inf 即可。

既然可以拿 \(2\) 个物品，就可以考虑在转移时枚举手里抓的两个物品 \(j,k\)，用当前状态加上拿这两个物品的耗时更新拿了这两个物品的状态。好吧貌似有点绕

具体而言，先枚举当前状态 \(i\)，再枚举 \(j,k\) 表示手里抓的物品，那么拿了 \(j,k\) 的状态就应该为 i|(1<<j-1)|(1<<k-1)，注意判断当前状态不包含手里的物品，即 \(i\) 的第 \(j,k\) 位为 \(0\)。

为方便可以先初始化了 \(i,j\) 间的耗时，记为 \(dist_{i,j}\)

for(ll i=0;i<ss;i++){
	if(dp[i]<0x3f3f3f3f){
		for(ll j=1;j<=n;j++){
			if(((i>>(j-1))&1)==0){
				for(ll k=1;k<=n;k++){
					if(((i>>(k-1))&1)==0){//j,k 当前状态不能有
						nans=dp[i]+dist[0][j]+dist[j][k]+dist[k][0];
						if(dp[i|(1<<(j-1))|(1<<(k-1))]>nans){
							dp[i|(1<<(j-1))|(1<<(k-1))]=nans;
							pos[i|(1<<(j-1))|(1<<(k-1))]=i;
						}
					}
				}
				break;
			}
		}
	}
}

---

考虑如何输出路径。

根据套路，在转移的时候设一个 \(pos\) 表示状态转移来源，然后递归处理即可。

inline void print(ll now){
	if(now==0){
		return ;
	}
	cout<<"0 ";
	for(ll i=1;i<=n;i++){
		if(((now^pos[now])>>(i-1))&1){
			cout<<i<<" ";
		}//now^pos[now] 即为在这一轮转移过程中被新拿了的物品
	}
	print(pos[now]);
}

完整 code 就不放辣。