80分玄关求条,已经快改成题解的样子了
  • 板块P1433 吃奶酪
  • 楼主Z_kazuha
  • 当前回复2
  • 已保存回复2
  • 发布时间2025/1/2 20:32
  • 上次更新2025/1/3 13:26:29
查看原帖
80分玄关求条,已经快改成题解的样子了
1419569
Z_kazuha楼主2025/1/2 20:32
#include <bits/stdc++.h>
using namespace std;
//#define double long double
int n,sum;
double x[20],y[20];
double a[20][20],f[20][1<<17],ans;
double dis(double x,double y,double x1,double y1){
	return sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y));
}
signed main(){
	cin>>n;
	sum=(1<<n)-1;
	memset(f,127,sizeof(f));
    ans=f[0][0];
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			a[i][j]=a[j][i]=dis(x[i],y[i],x[j],y[j]);
			f[i][1<<(i-1)]=dis(x[i],y[i],0.0,0.0);
		}
	}
	for(int k=1;k<=sum;k++){
		for(int i=1;i<=n;i++){
			if((k&(1<<(i-1)))==0)continue;
			for(int j=1;j<=n;j++){
				if(j==i)continue;
				if((k&(1<<(j-1)))==0)continue;
				//if((!(k&(1<<(i-1))))||(!(k&(1<<(j-1)))))continue;
				f[i][k]=min(f[i][k],f[j][k-(1<<(i-1))]+a[i][j]);	
			}
		}
	}
	for(int i=1;i<=n;i++)ans=min(ans,f[i][sum]);
	printf("%.2lf",ans);
	return 0;
}
2025/1/2 20:32
加载中...