自动搬运

查看原文

来自洛谷，原作者为

	NTT__int128 可爱捏！||喵~

搬运于2025-08-24 22:41:54，当前版本为作者最后更新于2024-06-07 16:48:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8733 [蓝桥杯 2020 国 C] 补给 题解

一道最短路加状压题。

首先，处理出每两个点 $i,j$ 之间的最短距离 $dis_{i,j}$。

然后，开始状压。

定义 $dp_{i,j}$ 为在状态为 $i$ 且停留在 $j$ 的最短距离。其中，状态 $i$ 在二进制下从后往前的第 $k$ 位表示第 $k$ 个点是否到达（$0$ 表示没到达，$1$ 表示到达了）。

初始：$dp_{1,0}=1$。

转移：$dp_{i,j} = \min dp_{i\oplus 2^j,k} + dis_{j,k}$（从状态 $i\oplus 2^j$ 来，答案为状态为 $i\oplus 2^j$ 且停留在 $k$ 的答案 $dp_{i\oplus 2^j,k}$ 加上从 $k$ 到 $j$ 的距离）。要求：$i\oplus 2^j$ 从后往前的第 $k$ 位不为 $0$。

答案：$\min\limits_{i=1}^{n-1}dp_{2^n-1,i}+dis_{i,0}$。

注意：

1. 别忘了最后得回去；

2. 最短路初始建边若边长大于 $D$，就不能建。

题外话：考场上最后几分钟才改成了状压的写法，没调出来（悲）。

代码：

#include <bits/stdc++.h>
using namespace std ;
int n , d ;
double ans = DBL_MAX , x[25] , y[25] , dp[1 << 20][25] , dis[25][25] ;
bool vis[25] ;
double jl(int a , int b)
{
	return sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b])) ;
}
int main()
{
	memset(dp , 0x7f , sizeof dp) ;
	memset(dis , 0x7f , sizeof dis) ;
	cin >> n >> d ;
	for(int i = 0 ; i < n ; i++)	cin >> x[i] >> y[i] ;
	for(int i = 0 ; i < n ; i++)	for(int j = 0 ; j < n ; j++)	if(jl(i , j) <= d)	dis[i][j] = jl(i , j) ;
	for(int i = 0 ; i < n ; i++)
		for(int j = 0 ; j < n ; j++)
			for(int k = 0 ; k < n ; k++)
				dis[i][j] = min(dis[i][j] , dis[i][k] + dis[k][j]) ;
	dp[1][0] = 0 ;
	for(int i = 1 ; i < (1 << n) ; i++)
	{
		for(int j = 0 ; j < n ; j++)
		{
			if(!((i >> j) & 1))	continue ;
			int tmp = i ^ (1 << j) ;
			for(int k = 0 ; k < n ; k++)
			{
				if(!((tmp >> k) & 1))	continue ;
				dp[i][j] = min(dp[i][j] , dp[tmp][k] + dis[j][k]) ;
			}
		}
	}
	for(int i = 1 ; i < n ; i++)
		ans = min(ans , dp[(1 << n) - 1][i] + dis[i][0]) ;
	printf("%.2lf" , ans) ;
	return 0 ;
}