lanqiao oj 17136 星球（状态压缩dp）

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std ;
const int N = 20 , M = 110 ;;
double f[1<<N][20] ;
int x[M] ,y[M] , z[M] ,w[M] ;
double get_dis(int a ,int b ){//求直线距离 
  return sqrt((x[a]-x[b])*(x[a]-x[b]) + (y[a] - y[b]) * (y[a] -y[b]) + (z[a] - z[b]) * (z[a]-z[b])) ;
}
int main(){
  int n ;
  cin >> n ;
  for(int i = 0  ;i < n ; i++){
    cin >> x[i] >> y[i] >> z[i] >>w[i];
  }
  memset(f,127,sizeof(f));
  f[0][0] = 0 ;
  for(int i = 0 ; i < n ; i ++) f[1<<i][i] = 0 ;
  for(int i = 0 ; i < 1 << n  ; i++){
    for(int j = 0 ; j < n ; j ++){
      for(int k = 0 ; k < n ; k ++){
        if((i>>j&1) && (i ^(1<<j)) >> k & 1) {//1. j存在于i中 2. k 于 j 不相等 ，并且k存在于i中 
          f[i][j] = min(f[i][j] , f[i ^(1<<j)][k] + get_dis(k,j) * w[j]);
        }
      }
    }
  }
  double ans = f[(1<<n)-1][0] ;
  for(int i = 1 ; i < n ; i ++) ans = min(ans , f[(1<<n)-1][i]) ;
  printf("%.2lf" , ans) ; 
}