WA on #10 #11 #12 #13 90分 求调
查看原帖
WA on #10 #11 #12 #13 90分 求调
1173109
OrientDragon楼主2024/8/19 13:46
#include <bits/stdc++.h>
using namespace std;

int n;
const int N = 15;
double x[N], y[N];
double dp[(1 << N) - 1][N];
double ans = (1 << 30);

double dist(double xa, double ya, double xb, double yb) {
	return sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));
}

int main() {
	cin >> n;
	for(int i = 0; i < n; i ++)
		cin >> x[i] >> y[i];
	memset(dp, 127, sizeof(dp));
	for(int i = 0; i < n; i ++)
		dp[(1 << i)][i] = dist(x[i], y[i], 0, 0);
	for(int S = 0; S < (1 << n); S ++)
		for(int xx = 0; xx < n; xx ++)
			if(S & (1 << xx))
				for(int i = 0; i < n; i ++)
					if((S & (1 << i)) && i != xx)
						dp[S][xx] = min(dp[S][xx], dp[S - (1 << xx)][i] + dist(x[i], y[i], x[xx], y[xx]));
	for(int i = 0; i < n; i ++)
		ans = min(ans, dp[(1 << n) - 1][i]);
	printf("%.2f", abs(ans));
}
2024/8/19 13:46
加载中...