剪枝遇阻(read n是什么鬼。。。)
  • 板块P1433 吃奶酪
  • 楼主Snowmiku
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/7/30 15:32
  • 上次更新2023/11/6 21:46:18
查看原帖
剪枝遇阻(read n是什么鬼。。。)
363334
Snowmiku楼主2020/7/30 15:32
#include<bits/stdc++.h>
using namespace std;
double a[20]={0},b[20]={0},jl[20][20]={0},ans=1000000,s;
int n;
bool c[20]={0};
void dfs(int x,int m)
{
	if(m==0){
	 	ans=min(s,ans);
	 	return;
	 }
	for(int i=1;i<=n;i++){
		if(m==n)
		s=0;
		if(c[i]==0){
		c[i]=1;
		s+=jl[i][x];
		if(s>ans){
			c[i]=0;
			s-=jl[i][x];
			continue;
		}
		dfs(i,m-1);
		c[i]=0;
		s-=jl[i][x];
		}
	}
}
int main()
{
	cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i]>>b[i];
    for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++)
    jl[i][j]=sqrt((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j]));
    dfs(0,n);
    printf("%0.2llf\n",ans);
    return 0;
}
2020/7/30 15:32
加载中...