Language: C++

#include<iostream>
#include<vector>
#include<map>
#include<cmath>
#include<iomanip>
using namespace std;

class disjoint_set{
public:
  vector<int> v;
  disjoint_set(int n){
    v = vector<int>(n);
    for(int i=0;i<n;++i)v[i]=i;
  }
  int find(int x){
    if(v[x]==x)return x;
    else return v[x]=find(v[x]);
  }
  void unite(int x, int y){
    x=find(x);
    y=find(y);
    if(x==y)return ;
    v[x]=y;
  }
  bool same(int x,int y){return find(x)==find(y);}
};

struct edge{
  int src,dst;
  double cost;
  edge(int src,int dst,double cost):src(src),dst(dst),cost(cost){}
  bool operator<(const edge &t)const{return cost<t.cost;}
};

const int N = 14;
int n;
double res;
double p[2*N][2];
double dist[2*N][2*N];
double memo[2*N][2][1<<N][2];

double calc_dist( double p[2], double q[2] ){
  return sqrt(pow(p[0]-q[0],2.)+pow(p[1]-q[1],2.));
}

double pre_calc()
{
  for(int i = 0; i < 2*N; ++i){
    for(int j = 0; j < 2*N; ++j){
      dist[i][j] = calc_dist(p[i],p[j]);
    }
  }
  for(int i = 0; i < 2*N; ++i){
    for(int j = 0; j < 2; ++j){
      for(int k = 0; k < (1<<N); ++k){
        for(int l = 0; l < 2; ++l){
          memo[i][j][k][l] = 0;
        }
      }
    }
  }
}

double mst(int n, double p[2*N][2])
{
  vector<edge> e;
  disjoint_set ds(2*n);
  double ret = 0;
  
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      for(int k = 0; k < 2; ++k){
        for(int l = 0; l < 2; ++l){
          e.push_back(edge(2*i+k,2*j+l,dist[2*i+k][2*j+l]));
        }
      }
      if( i == j ){
        ds.unite(2*i,2*i+1);
        ret += dist[2*i][2*i+1];
      }
    }
  }

  sort(e.begin(),e.end());

  for(int i = 0; i < (int)e.size(); ++i){
    int src=e[i].src;
    int dst=e[i].dst;
    if(ds.same(src,dst)){
      continue;
    }else{
      ret += dist[src][dst];
      ds.unite(src,dst);
    }
  }
  return ret;
}

int call = 0;

double h(int cur, int  type, int vis, int depth){
  double ret = memo[cur][type][vis][depth%2];
  if( ret > 0 ) return ret;
  for(int i = 0; i < n; ++i){
    if( !(vis&(1<<i)) ){
      ret += min( dist[2*cur+type][2*i], dist[2*cur+type][2*i+1] );
    }
  }
  ret -= depth%2==1?dist[2*cur+type][2*cur+(type^1)]:0;
  memo[cur][type][vis][depth%2] = ret;
  return ret;
}

void rec(int cur, int type, int vis, int depth, double rem, double cost)
{
  ++call;
  //if( call % 50000000 ==0 ) cout << call << endl;
  //cout << cur << ' ' << type << endl;
  if( vis == (1<<n)-1 ){
    res = min(res,cost);
    return ;
  }
  if( cost + rem > res ) return ;
  
  if( depth % 2 == 0 ){
    double d = dist[2*cur+type][2*cur+(type^1)];
    rec(cur,type^1,vis|(1<<cur),depth+1,rem-d,cost+d);
  }else{
    for(int i = 0; i < n; ++i){
      if( !(vis & (1<<i)) ){
        for(int j = 0; j < 2; ++j){
          rec(i,j,vis,depth+1,rem,cost+dist[2*cur+type][2*i+j]);
        }
      }
    }
  }
}

int main()
{
  int tc=1;
  while(true){
    double rem = 0;

    cin >> n;
    if( n == 0 ) break;
    
    for(int i = 0; i < n; ++i){
      for(int j = 0; j < 2; ++j){
        for(int k = 0; k < 2; ++k){
          cin >> p[2*i+j][k];
        }
      }
    }
    pre_calc();
    for(int i = 0; i < n; ++i){
      rem += dist[2*i][2*i+1];
    }

    res = 2*mst(n,p)+1e-5;
    //cout << res << endl;
    //res = 101.685;
    call = 0;
    for(int i = 0; i < n; ++i){
      for(int j = 0; j < 2; ++j){
        rec(i,j,0,0,rem,0);
      }
    }
    //cout << call << endl;
    

    cout << "Case " << tc << ": " << fixed << setprecision(8) << res << endl;
    ++tc;
  }
  return 0;
}

Compiler output:
a.cc: In function 'double pre_calc()':
a.cc:62:1: warning: no return statement in function returning non-void [-Wreturn-type]
   62 | }
      | ^
a.cc: In function 'double mst(int, double (*)[2])':
a.cc:84:3: error: 'sort' was not declared in this scope; did you mean 'sqrt'?
   84 |   sort(e.begin(),e.end());
      |   ^~~~
      |   sqrt