深搜最后一个点T了,求救大佬剪枝或者其他方法qaq
查看原帖
深搜最后一个点T了,求救大佬剪枝或者其他方法qaq
480486
倚窗听雨落楼主2021/4/25 16:15
#include <bits/stdc++.h>
using namespace std;
int n;
double x[25];
double road=0;
double ans=0xffffff;
double y[25];
bool vis[25];
 void dfs(double x1,double y1,int num)
{
    if(num==n+1) {ans=min(ans,road);return;}
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            vis[i]=1;
            road+=sqrt(pow(x[i]-x1,2)+pow(y[i]-y1,2));
            if(road>ans) {
                vis[i]=0;
                road-=sqrt(pow(x[i]-x1,2)+pow(y[i]-y1,2));
                continue;
                }
            dfs(x[i],y[i],num+1);
            vis[i]=0;
            road-=sqrt(pow(x[i]-x1,2)+pow(y[i]-y1,2));
        }
    }
    return;
}
int main()
{
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    memset(vis,0,sizeof(vis));
    cin>>n;
    for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
    dfs(0,0,1);
    printf("%.2f\n",ans);
    return 0;
}
2021/4/25 16:15
加载中...