爆搜剪枝,不状压tle代码还有救吗?(玄关
  • 板块P1433 吃奶酪
  • 楼主Greeper
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/8 22:51
  • 上次更新2024/10/9 14:12:08
查看原帖
爆搜剪枝,不状压tle代码还有救吗?(玄关
1311900
Greeper楼主2024/10/8 22:51
#include<bits/stdc++.h>
using namespace std;
double x[20],y[20];
int s[20],st;
bool f[20];
double sum;
int n;
double minn=INT_MAX;
void findp(int dep,double nx,double ny)
{
    if(dep==n)
    {
        minn=min(sum,minn);
        return;
    }
    if(sum>=minn)
    {
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!f[i])
        {
            f[i]=1;
            s[++st]=i;
            double tx=x[s[dep+1]],ty=y[s[dep+1]];
            sum+=sqrt((tx-nx)*(tx-nx)+(ty-ny)*(ty-ny));
            findp(dep+1,tx,ty);
            sum-=sqrt((tx-nx)*(tx-nx)+(ty-ny)*(ty-ny));
            s[st--]=0;
            f[i]=0;
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
    findp(0,0,0);
    printf("%.2f",minn);
    return 0;
}
2024/10/8 22:51
加载中...