https://www.luogu.com.cn/problem/P1433
题目描述
房间里放着 n 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 (0,0) 点处。

输入格式
第一行一个正整数 n。

接下来每行 2个实数，表示第i块奶酪的坐标。

两点之间的距离公式为 sqrt ( x^2 + y^2 );
输出格式
一个数，表示要跑的最少距离，保留 2 位小数。

输入输出样例
输入
4
1 1
1 -1
-1 1
-1 -1
输出
7.41
说明/提示
1≤n≤15。

dp[ i ][ j ] 表示已经走过的城市为 i ( 已经走过的地方 每一个用一位 1/0 表示是否走过，压缩为 i )，当前所在的城市为 j 的最短路程。
相应的状态转移方程为dp[ i ][ j ]=min( dp[ i ^ (1<<j) ][ k ] + dis[ k ][ j ] ); i ^ (1<<j) 的意思是将 j 这个城市从 i 状态中去掉。 dis[ k ][ j ] 是 k 和 j 之间的距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sf(n) scanf("%d",&n)
#define pf(n) printf("%d",n)
#define pfc(c) printf(c)
#define fi(i,s,t) for(int i=s;i<t;i++)
#define fd(s,t) for(int i=s-1;i>=t;i--)
#define mem(a,c) memset(a,c,sizeof(a))
const double INF=0x3f3f3f3f;
const int MAX=17;
const int N=1<<15;
int n;
double dis[MAX][MAX],ans,dp[N][MAX],x[MAX],y[MAX];
int main(){
	freopen("in","r",stdin);
	sf(n);
	x[0]=0;y[0]=0;
	fi(i,1,n+1){
		scanf("%lf",&x[i]);scanf("%lf",&y[i]);
	}
	fi(i,0,n+1)
		fi(j,i+1,n+1){
			dis[i][j] = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
			dis[j][i] = dis[i][j];
		}
	fi(s,0,1<<n){                 //用 s 表示已经访问过的城市集合 
		fi(i,1,n+1){
			if(s&(1<<(i-1))){     //如果 i 点 在 s 中 
				if(s==(1<<(i-1))) //s 中只有 i 
					dp[s][i] = dis[0][i];
				else {
					dp[s][i]=INF;
					fi(j,1,n+1){
						if(s&(1<<(j-1)) && j!=i){   //  s^(1<<(i-1)) 从 s 中去掉 j  
							dp[s][i]=min(dp[s^(1<<(i-1))][j]+dis[j][i],dp[s][i]);
						}
					}
				}
			}
		}
	}
	ans =dp[(1<<n)-1][1];
	fi(i,2,n+1)
		if(dp[(1<<n)-1][i] < ans)
			ans = dp[(1<<n)-1][i];
	printf("%.2lf",ans);
	return 0;
}