UVa Q10911 (DFS)

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

int arr[16][2];
double dist(int p, int q){
    return sqrt((arr[p][0]-arr[q][0]) * (arr[p][0]-arr[q][0]) + (arr[p][1]-arr[q][1]) * (arr[p][1]-arr[q][1]));
}

bool vis[16];
double ans, len;
int n;
void dfs(int depth){
    if(len >= ans)return;
    if(depth == n){
        ans = len;
    }else{
        int one, two;
        for(int i = 0; i < n*2; ++i){
            if(!vis[i]){
                one = i;
                vis[one] = 1;
                break;
            }
        }
        for(int i = one+1; i < n*2; ++i){
            if(!vis[i]){
                two = i;
                len += dist(one, two);
                vis[two] = 1;
                dfs(depth+1);
                vis[two] = 0;
                len -= dist(one, two);
            }
        }
        vis[one] = 0;
    }
}

int32_t main(){
    string aux;
    int cnt = 0;
    while(cin >> n){
        if(n == 0)break;
        ans = INT_MAX;
        len = 0;
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < n*2; ++i){
            cin >> aux >> arr[i][0] >> arr[i][1];
        }
        dfs(0);
        printf("Case %d: %.2f\n", ++cnt, ans);
    }
    return 0;
}