状态压缩DP,样例不过求调
查看原帖
状态压缩DP,样例不过求调
1025958
511_Juruo_wyk楼主2024/4/4 21:31

样例输出 1.411.41,一直找不到问题,后来和题解区对照了一下,和第二篇题解除了变量名之外没什么区别(一些我省略的扩号加上了也不行,所以应该不是位运算优先级的问题),求大佬修改,谢谢

#include<bits/stdc++.h>
using namespace std;
typedef double db;
const int N = 25,M = (1<<15)+5;
struct node{
	db x,y;
}a[N];
db from(node a,node b){return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));}
db way(int x,int y){return from(a[x],a[y]);}
db dp[N][M],ans=0x3f3f3f3f;
int n;
int main(){
	cin>>n;
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=n;i++)
		scanf("%lf %lf",&a[i].x,&a[i].y);
	for(int s=1;s<(1<<n);s++)
		for(int i=1;i<=n;i++){
			if(s&(1<<i-1)==0)continue;
			if(s==(1<<i-1))dp[i][s]=0;
			for(int j=1;j<=n;j++){
				if(i==j||s&(1<<j-1)==0)continue;
				dp[i][s]=min(dp[i][s],dp[j][s-(1<<i-1)]+way(j,i));
			}
		}
	for(int i=1;i<=n;i++)
		ans=min(ans,dp[i][(1<<n)-1]+way(0,i));
	printf("%.2lf",ans);
	return 0;
}
2024/4/4 21:31
加载中...