UVa 10911 - Forming Quiz Teams

// UVa 10911 - Forming Quiz Teams

#include <iostream>
#include <string.h>
#include <cmath>
#include <float.h>
#include <stdio.h>
using namespace std;

#define datatype unsigned long long int

int n;
double T[65536];
double x[16], y[16];
double oo = DBL_MAX;
double D[16][16];

double calc(datatype config) {
	if (T[config] != oo)
		return T[config];
	for (int i = 0; i < n; i++)
		if ((config >> i) % 2 == 1)
			for (int j = i + 1; j < n; j++)
				if ((config >> j) % 2 == 1) {
					datatype child = config - (1 << i) - (1 << j);
					double child_cost = calc(child) + D[i][j];
					if (T[config] > child_cost)
						T[config] = child_cost;
				}
	return T[config];
}

int main() {
	datatype power[16];
	power[0] = 1;
	for (int i = 1; i <= 16; i++)
		power[i] = power[i - 1] * 2;

	cin >> n;
	int cases = 0;
	while (n) {
		cases++;
		n = n * 2;
		string name;
		for (int i = 0; i < n; i++)
			cin >> name >> x[i] >> y[i];
		for (int i = 0; i < n; i++)
			for (int j = i + 1; j < n; j++)
				D[i][j] = pow((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]), 0.5);
		T[0] = 0;
		for (datatype c = 1; c < power[n]; c++)
			T[c] = oo;
		calc(power[n] - 1);
		printf("Case %d: %.2f\n", cases, T[power[n] - 1]);
		cin >> n;
	}

	return 0;
}