WA on #5 #12 #13
题目

#include <bits/stdc++.h>
#define PII pair <int, int>
#define LL long long
#define DB double

namespace FastIO
{
	inline void read(int MOD, int &ret){
		ret = 0;
		char ch = getchar();int ngtv = 1;
		if(MOD == 0) {while(ch < '0' || ch > '9'){if(ch == '-') ngtv = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){ret = (ret << 3) + (ret << 1) + (ch ^ 48);ch = getchar();}}
		else {while(ch < '0' || ch > '9'){if(ch == '-') ngtv = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){ret = (((ret << 3) + (ret << 1)) % MOD + (ch ^ 48) % MOD) % MOD;ch = getchar();} }
		ret *= ngtv;}
	inline void cread(char &ch){ch=getchar();while(ch == ' ' || ch == '\n' || ch == '\r' || ch == 0) ch = getchar();}
}
using namespace FastIO;
using namespace std;

int n, c, cnt, pw[20];
double ans = 0, g[20][20], dp[20][35000];
struct Node
{
	double x, y;
}a[20];

double gap(int x, int y)
{
	return sqrt((a[x].x - a[y].x) * (a[x].x - a[y].x) + (a[x].y - a[y].y) * (a[x].y - a[y].y));
}

signed main()
{
//	freopen("P1433_5.in", "r", stdin);
	read(0, n);
	a[0] = {0, 0};
	for(int i = 1; i <= n; i ++ )
		scanf("%lf%lf", &a[i].x, &a[i].y);
	
	for(int i = 0; i <= n; i ++ )
	{
		for(int j = i + 1; j <= n; j ++ )
			g[i][j] = g[j][i] = gap(i, j);
	}
	
	pw[0] = 1;
	for(int i = 1; i <= n; i ++ )
		pw[i] = pw[i - 1] << 1;
	cnt = pw[n] - 1;
	
	memset(dp, 127, sizeof dp);
	ans = dp[0][0];
	for(int i = 1; i <= n; i ++ )
		dp[i][pw[i - 1]] = g[0][i];
	
	for(int i = 1; i <= cnt; i ++ )
	{
		for(int j = 1; j <= n; j ++ )
		{
			if(i & pw[j - 1] == 0)
				continue;
			for(int k = 1; k <= n; k ++ )
			{
				if(j == k)
					continue;
				if(i & pw[k - 1] == 0)
					continue;
				dp[j][i] = min(dp[j][i], dp[k][i - pw[j - 1]] + g[j][k]);
			}
		}
	}
	
	for(int i = 1; i <= n; i ++ )
		ans = min(ans, dp[i][cnt]);
	printf("%.2f\n", ans);
	
    return 0;
}