暴搜求助
  • 板块学术版
  • 楼主Eason_cyx大愚若智
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/3/12 11:45
  • 上次更新2023/10/23 21:47:40
查看原帖
暴搜求助
741244
Eason_cyx大愚若智楼主2023/3/12 11:45
#include <bits/stdc++.h>
using namespace std;
int x[15],y[15],a[15];
bool vis[15];
double minn = 0x7f7f7f7f;
int n;
double distance(int q1,int q2,int w1,int w2)
{
    return sqrt((q1 - q2) * (q1 - q2) + (w1 - w2) * (w1 - w2));
}
void dfs(int step)
{
    if(step > n)
    {
        double ans = distance(0,0,x[a[1]],y[a[1]]);
        for(int i = 2;i <= n;i++)
        {
            ans += distance(x[a[i-1]],y[a[i-1]],x[a[i]],y[a[i]]);
        }
        minn = min(minn,ans);
        return;
    }
    for(int i = 1;i <= n;i++)
    {
        if(vis[i]) continue;
        vis[i] = true;
        a[step] = i;
        dfs(step+1);
        vis[i] = false;
    }
}
int main() 
{
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> x[i] >> y[i];
    dfs(1);
    cout << fixed << setprecision(2) << minn << endl;
    return 0;
}
2023/3/12 11:45
加载中...