社区讨论

样例过,全MLE,蒟蒻求调

P1433吃奶酪参与者 5已保存回复 9

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@lo8koylo
此快照首次捕获于
2023/10/27 20:11
2 年前
此快照最后确认于
2023/10/27 20:11
2 年前
查看原帖
CPP
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<iomanip>
using namespace std; 
int n;
double a[20][20],ans;
double x[20],y[20],f[18][37000];
double jl(int u,int v){
	return sqrt((x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]));
}
int main(){
	memset(f,127,sizeof(f));
	ans=f[0][0];
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	x[0]=0;y[0]=0;
	for(int i=0;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			a[i][j]=jl(i,j);
			a[j][i]=a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		f[i][(1<<(i-1))]=a[0][i];
	}
	for(int s=1;s<(1<<n);s++){
		for(int i=1;i<=n;i++){
			if((s&(1<<(i-1)))==0)continue;
			for(int j=1;j<=n;j++){
				if(i==j)continue;
				if((s&(1<<(j-1)))==0)continue;
				f[i][s]=min(f[i][s],f[j][s-(1<<(i-1))]+a[i][j]);
			}
		}
	}
	for(int i=1;i<=n;i++)
	ans=min(ans,f[i][(1<<n)-1]);
	cout<<fixed<<setprecision(2)<<ans;
}
//ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC

回复

9 条回复,欢迎继续交流。

正在加载回复...