社区讨论

#12 #13WA,玄关求调

P1433吃奶酪参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mln6oh6t
此快照首次捕获于
2026/02/15 11:26
4 天前
此快照最后确认于
2026/02/19 13:45
3 小时前
查看原帖
dfs最优性剪枝:
CPP
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;
double x[MAXN],y[MAXN];
int n;
double ans = 1e6,dis[MAXN][MAXN];
int cnt = 0;
bool d[MAXN];

void dfs(int k,int sum,double all) {
    cnt++;
    if(cnt >= 1e7) {
        printf("%.2f",ans);
        exit(0);
    }
    if(sum >= n) {
        if(all < ans) ans = all;
        return ;
    }
    for(int i = 1;i <= n;i++) {
        if(d[i]) continue;
        double t = all + dis[i][k];
        if(t >= ans) continue;
        
        d[i] = true;
        dfs(i,sum + 1,all + dis[i][k]);
        d[i] = false;
    }
}

int main() {

    scanf("%d",&n);

    x[0] = y[0] = 0;
    
    for(int i = 1;i <= n;i++) {
        scanf("%lf",&x[i],&y[i]);
        d[i] = false;
    }

    for(int i = 0;i <= n;i++) {
         for(int j = 0;j <= n;j++) {
            if(i != j) dis[i][j] = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
        }       
    }

    dfs(0,0,0.0);
    printf("%.2f",ans);
}

回复

3 条回复,欢迎继续交流。

正在加载回复...