WA 60求助
查看原帖
WA 60求助
270791
WanderingTrader楼主2020/7/21 13:33

刚刚学状压dp,希望大佬帮忙看看哪有问题

#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define N 16
#define INF 1e12
ld d[N][N],x[N],y[N],dp[1<<N];
int n;
ld dist(int i,int j)
{
	ld a = x[i]-x[j],b = y[i]-y[j];
	return sqrt(a*a+b*b);
}
int main()
{
	scanf("%d",&n);
	for(int i = 1;i <= n;++i)
	{
		scanf("%Lf%Lf",x+i,y+i);
		for(int j = 0;j < i;++j)
			d[i][j] = d[j][i] = dist(i,j);
	}
	if(n==1){printf("%.2Lf\n",d[1][0]);return 0;}
	int nptr = (1<<n);
	for(int i = 1;i < nptr;++i) dp[i] = INF;
	for(int i = 0;i < n;++i) dp[1<<i] = dist(i+1,0);
	for(int i = 1;i < nptr;++i)
	{
		if(dp[i]!=INF) continue;
		for(int j = 0;j < n;++j) if(i&(1<<j))
			for(int k = 0;k < n;++k) if(i&(1<<k)&&j!=k)
				dp[i] = min(dp[i],dp[i-(1<<j)]+d[k+1][j+1]);
	}
	printf("%.2Lf\n",dp[nptr-1]);
	return 0;
}
2020/7/21 13:33
加载中...