20分求助
  • 板块P1433 吃奶酪
  • 楼主q1uple
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/7/23 08:38
  • 上次更新2023/10/27 18:49:51
查看原帖
20分求助
539133
q1uple楼主2022/7/23 08:38
#include<bits/stdc++.h>
using namespace std;
double x[16],y[16];
double dp[16][16]={0};
int vis[16]={0};
int n;
double minn=1919810.114514;

double dis(int a,int b)
{
	sqrt(abs(x[a]-x[b])*abs(x[a]-x[b])+abs(y[a]-y[b])*abs(y[a]-y[b]));
}
void dfs(int k,double sum,int p)
{
	if(k==n)
	{
		minn=min(minn,sum);
	}
	if(sum>minn)
	{
		return;
	}
	for(int i=1;i<=n;i++)
	{
			if(!vis[i])
			{
            	if(dp[p][i]!=0)
				{
           	    	vis[i]=true;
          	      	dfs(k+1,sum+dp[p][i],i);
          	    	vis[i]=false;
            	}
           	 	else if(dp[i][p]!=0)
				{	
					vis[i]=true;
          	      	dfs(k+1,sum+dp[i][p],i);
          	    	vis[i]=false;
            	}
            	else
				{
               	 	vis[i]=true;
                	dp[i][p]=dis(i,p);
                	dfs(k+1,sum+dp[i][p],i);
                	vis[i]=false;
            	}
			}
	}
}

int main()
{
	
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i]>>y[i];
	}
	dfs(1,0.0,0);
	printf("%.2f",minn);
}
2022/7/23 08:38
加载中...