萌新初学状压,编译失败求调
查看原帖
萌新初学状压,编译失败求调
809165
The_Wandering_Earth楼主2023/1/18 15:43

rt,本人太蒻了,实在看不出来哪里错了

#include<bits/stdc++.h>
using namespace std;
#define maxn (1<<16)
#define min(a,b) (((a)<(b))?(a):(b))
int n;
double ans,a[20][20],x[20],y[20],f[20][maxn];
double distance(int u,int v){
	return sqrt((x[v]-x[u])*(x[v]-x[u])+(y[v]-y[u])*(y[v]-y[u]));
}
signed 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]=distance(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 k=1;k<(1<<n);k++){
		for(int i=1;i<=n;i++){
			if(k&(1<<(i-1))==0)continue;
			for(int j=1;j<=n;j++){
				if(i==j||k&(1<<(j-1))==0)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][(1<<n)-1]);
	}
	printf("%.2f",ans);
    return 0; 
}
2023/1/18 15:43
加载中...