DFS 90分 最后一个点还能优化吗
  • 板块P1433 吃奶酪
  • 楼主Lhz1313
  • 当前回复19
  • 已保存回复19
  • 发布时间2020/8/10 19:14
  • 上次更新2023/11/6 20:43:11
查看原帖
DFS 90分 最后一个点还能优化吗
311830
Lhz1313楼主2020/8/10 19:14
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include<queue>
using namespace std;
double minm=1e+9,a[15][2];
int n;
bool b[15];
void dfs(double x,double y,int now,double sum)
{
    if(now==n+1)
    {
        if(minm>sum)
        minm=sum;
    }
    else
    {
        for(int i=0;i<n;i++)
        {
            if(b[i]==true)
            {
                double ll=sum+sqrt((a[i][0]-x)*(a[i][0]-x)+(a[i][1]-y)*(a[i][1]-y));
                if(ll>minm)
                return ;
                else
                {
                    b[i]=false;
                    dfs(a[i][0],a[i][1],now+1,ll);
                    b[i]=true;
                }
            }
        }
    }
    
}
int main()
{
    cin>>n;
    memset(b,true,sizeof(b));
    for(int i=0;i<n;i++)
    cin>>a[i][0]>>a[i][1];
    dfs(0,0,1,0);
    printf("%.2lf",minm);
    system("pause");
    return 0;
}
2020/8/10 19:14
加载中...