90分状压dfs求助,最后一个点T了
  • 板块P1433 吃奶酪
  • 楼主_HHJ
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/6/12 11:06
  • 上次更新2023/10/27 23:28:36
查看原帖
90分状压dfs求助,最后一个点T了
600112
_HHJ楼主2022/6/12 11:06
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
typedef pair<double,double> PII;

#define F(i,j,k)    for(int (i) = j ; i <= (k); i++ )
#define F2(i,j,k)   for(int (i) = j ; i < (k); i++ )
#define F3(i,j,k)   for(int  i = j ; i >= k ; i-- )
#define fi first
#define se second

int n;
double ans = 10000000000;
double xy[50000];
PII a[30];

double dt(int num,int i)
{
    if(xy[ 1 << num | 1 << i] == 0)
    {
        double x = a[num].fi,y=a[num].se;
        double x2 = a[i].fi,y2=a[i].se; 
        return xy[1 << num || 1 << i]  = sqrt((x-x2) * (x - x2) + (y-y2)*(y - y2));
    }
    
    return xy[1 << i | 1 << num];
}


void dfs(int u,int st,int now,double res)
{
    if(res >= ans)return;//剪枝
    if(u == n)//如果都选过了
    {
        ans = min(res ,ans);//判断最小值
        return;
    }
    F(i,1,n)
    {
        if(st >> i & 1)continue;//选过
        dfs(u + 1,st +(1 << i),i,res + dt(now,i));
    }
}


int main()
{
    cin >> n;
    a[0].fi = 0,a[0].se = 0;//起点
    F(i,1,n) scanf("%lf%lf",&a[i].fi,&a[i].se);
    F(i,0,n)
        F(j,i+1,n)
        xy[1 << i | 1 << j] = dt(i,j);
    dfs(0,0,0,0);
    printf("%.2lf",ans);//输出



}
2022/6/12 11:06
加载中...