有没有那个大佬能帮我看看,还有什么可以优化的吗?谢谢!!
  • 板块P1433 吃奶酪
  • 楼主Ryan_L_F
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/12/15 09:29
  • 上次更新2024/12/15 11:57:48
查看原帖
有没有那个大佬能帮我看看,还有什么可以优化的吗?谢谢!!
1022974
Ryan_L_F楼主2024/12/15 09:29
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int n;
double x[N], y[N], ans = 2000000000.0;
bool vis[N];
double calc(double x1, double y1, double x2, double y2){
    double xx = (x1 - x2), yy = (y1 - y2);
    return sqrt(xx * xx + yy * yy);
}
void dfs(int step, double sum, double x1, double y1){
    if(sum >= ans)
        return ;
    if(step > n){
        ans = min(ans, sum);
        return ;
    }
    for(int i = 1; i <= n; i++)
        if(!vis[i]){
            vis[i] = 1;
            dfs(step + 1, sum + calc(x1, y1, x[i], y[i]), x[i], y[i]);
            vis[i] = 0;
        }
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];
    dfs(1, 0.0, 0.0, 0.0);
    printf("%.2lf\n", ans);
    return 0;
}
2024/12/15 09:29
加载中...