UVa 10911

tree-structure dp plus bitmask technics
state:
    dp[i] - minimum dist when we have formed groups indicated by i
    so when i==(1<<2*n)-1, all groups will be paired
transition:
    dp[i]=min(d[x][y]+dp[i|(1<<x)|(1<<y)]
    for all next states of i (set two bits to 1 each time), thus x, y are next pair, and d[x][y]
    is their distance

/* UVas */
/*****************************************************************************/
int n, c=1;
int s[16][2];
double d[16][16];
double dp[1<<16];
string t;
double dfs(int s) {
    double &r=dp[s];
    if (r>-1) {
        return r;
    } else if (s==(1<<2*n)-1) {
        r=0;
        return r;
    } else {
        r=1e9;
        for (int i=0; i<2*n; i++) {
            if (!(s&(1<<i))) {
                for (int j=i+1; j<2*n; j++) {
                    if (!(s&(1<<j))) {
                        r=min(r, d[i][j]+dfs(s|(1<<i)|(1<<j)));
                    }
                }
                break;
            }
        }
        return r;
    }
}
int main(void) {
    while (cin>>n&&n) {
        for (int i=0; i<2*n; i++) {
            cin>>t>>s[i][0]>>s[i][1];
        }
        for (int i=0; i<2*n; i++) {
            for (int j=0; j<2*n; j++) {
                int x0=s[i][0], y0=s[i][1];
                int x1=s[j][0], y1=s[j][1];
                d[i][j]=sqrt((double)(x0-x1)*(x0-x1)+(y0-y1)*(y0-y1));
            }
        }
        memset(dp, -1, sizeof(dp));
        printf("Case %d: %.2lf\n", c++, dfs(0));
    }
    return 0;
}
/*****************************************************************************/