社区讨论

70pt ,不是很明白为什么会wa,和题解也对比了,求大佬调

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

讨论操作

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

当前回复
2 条
当前快照
1 份
快照标识符
@lo1ov14m
此快照首次捕获于
2023/10/23 00:34
2 年前
此快照最后确认于
2023/11/03 01:15
2 年前
查看原帖
CPP
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
double dp[1<<15][15];//在i状态下,最后一部到第j块奶酪 
double map[25][25];
double x[1005],y[1005];

int main()
{int n;
 scanf("%d",&n);
 for(int i=1;i<=n;i++){
 	scanf("%lf%lf",&x[i],&y[i]);
 }
 
 memset(map,0x7f,sizeof(map));
 
 for(int i=0;i<=n;i++){
 	for(int j=1;j<=n;j++){
 		if(i==j) {
		 map[i][j]=0;
		 continue;
		}
 		map[i][j]=sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) );
 		map[j][i]=map[i][j];
	 }
 }
 
 
 memset(dp,0x7f,sizeof(dp));
 double ans=dp[0][0];
  
 for(int i=1;i<=n;i++){
 	dp[1<<i-1][1]=map[0][i];
 }
 
 
 for(int i=0;i< (1<<n);i++){
 	for(int j=1;j<=n;j++){
 		if( ( (1<< (j-1)) & i )== 0 ) continue;
 		for(int k=1;k<=n;k++){
 			if(j==k) continue;
 			if( (i & (1 << k-1) ) ==0) continue;
 			dp[i][j]=min(dp[i][j],dp[i ^ (1<< (j-1) ) ][k]+map[j][k]);
		 }
 		
	 }
 }

 for(int i=1;i<=n;i++)
    ans=min(ans,dp[(1<<n)-1][i]);
 printf("%.2lf",ans);
return 0;
}

回复

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

正在加载回复...