0分求助
  • 板块P1433 吃奶酪
  • 楼主A_Noob
  • 当前回复7
  • 已保存回复7
  • 发布时间2022/8/16 16:36
  • 上次更新2023/10/27 15:07:59
查看原帖
0分求助
549293
A_Noob楼主2022/8/16 16:36
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
double d[210][210];
int x[30],y[30];
int n;double ans=1e9;bool vis[30];

void dfs(int last, double sum,int u)
{
    if(u>n)
    {
        ans=min(ans,sum);
        return;
    }
    for(int i = 1; i <= n; i++)
    {
        if(vis[i]==1)continue;
        vis[i]=1;
        int w=d[last][i];
        dfs(i,w+sum,u+1);
        vis[i]=0;
    }
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> x[i] >> y[i];
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            d[i][j]=sqrt((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i]*(y[j]-y[i])));
        }
    }
    dfs(0,0,1);

    cout << ans;

}
2022/8/16 16:36
加载中...