Forming Quiz Teams

#include <bits/stdc++.h>
using namespace std;

#define ii pair<int, int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int OO = 0x3f3f3f3f; // 0x3f3f3f3f;

int n;
vector<ii> v;
double dp[1 << 17];
double seen[1 << 17];
int tempo = 1;

double sq(double x) {
    return x * x;
}

double dist(int i, int j) {
    return sqrt(sq(v[i].fi - v[j].fi) + sq(v[i].se - v[j].se));
}

double sol(int mask) {
    if(mask == ((1 << n) - 1))
        return 0;
    if(seen[mask] == tempo) return dp[mask];
    double ans = OO;
    for(int i = 0; i < n; ++i)
        for(int j = i + 1; j < n; ++j)
            if((mask & (1 << i)) == 0 and (mask & (1 << j)) == 0)
                ans = min(ans, sol(mask | (1 << i) | (1 << j)) + dist(i, j));
    seen[mask] = tempo;
    return dp[mask] = ans;
}

void solve(){
    int caso = 1;
    while(cin >> n and n) {
        n *= 2;
        string s;
        v.clear();
        v.resize(n);
        for(ii &a : v) cin >> s >> a.fi >> a.se;
        ++tempo;
        cout << "Case " << caso++ << ": " << fixed << setprecision(2) << sol(0) << '\n';
    }
}

int32_t main() {
    fastio;
    solve();
    return 0;
}