90分求调
查看原帖
90分求调
1713700
tangtianyao楼主2025/6/25 18:16

为什么只有90??90?? 直接气炸了

#include<bits/stdc++.h>

using namespace std;
using db = double;

int n;
db x[16], y[16], dp[16][(1 << 15)], ans = 1e9;

db dis(int a, int b){
  return sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));
}

int main(){
  cin >> n;
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= (1 << n); j++){
      dp[i][j] = 1e9;
    }
  }
  for(int i = 1; i <= n; i++){
    cin >> x[i] >> y[i];
    dp[i][1 << (i - 1)] = dis(i, 0);
  }
  for(int i = 1; i < (1 << n); i++){
    for(int j = 1; j <= n; j++){
      if((i & (1 << (j - 1))) == 0) continue;
      for(int k = 1; k <= n; k++){
        if(j == k || (i & (1 << (k - 1))) == 0) continue;
        dp[j][i] = min(dp[j][i], dp[k][i - (1 << (j - 1))] + dis(j, k));
      }
    }
  }
  for(int i = 1; i <= n; i++) ans = min(ans, dp[i][(1 << n) - 1]);
  cout << fixed << setprecision(2) << ans;
  return 0;
}

2025/6/25 18:16
加载中...