UVa 10911 - Forming Quiz Teams Solution

 #include <bits/stdc++.h>
using namespace std;
int n,N;
vector<vector<double> > coords;
vector<vector<double> > dp;
vector<vector<double> > dist;
double rec(int i, int mask){
if(i==N-1)
    return 0;
if(dp[i][mask]!=-1)return dp[i][mask];
if (mask&(1<<i)) return rec(i+1,mask);
double ans=(double)INT_MAX;
for(int j=i+1;j<N;j++)
    if((mask&(1<<j))==0)ans=min(ans,dist[i][j]+rec(i+1,mask|(1<<j)));
return dp[i][mask]=ans;
}
int main(){
    int cas=0;
    while(cin>>n){
        if(!n)return 0;
        N=2*n;
        coords.assign(N,vector<double>(2));
        for(int i=0;i<N;i++){
            string s;
            cin>>ws;
            cin>>s;
            cin>>coords[i][0]>>coords[i][1];
        }
        dist.assign(N,vector<double>(N));
        for(int i=0;i<N;i++)
            for(int j=i+1;j<N;j++){
                dist[i][j]=sqrt(((coords[i][0]-coords[j][0])*(coords[i][0]-coords[j][0])) + ((coords[i][1]-coords[j][1])*(coords[i][1]-coords[j][1])));
            }
        dp.assign(N,vector<double>((int)pow(2,N),-1));
        cout<<fixed<<"Case "<<++cas<<": "<<setprecision(2)<<rec(0,0)<<endl;
    }
    return 0;
}