2013年9月4日

UVa 10911 - Forming Quiz Teams

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

inline double dis(int x1, int y1, int x2, int y2) {
  return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main() {
  int bits[17] = {1};
  for (int b = 1; b < 17; b++) {
    bits[b] = bits[b - 1] << 1;
  }
  int N, C = 1;
  while (scanf("%d", &N) && N) {
    N <<= 1;
    int x[16], y[16];
    for (int i = 0; i < N; i++) {
      scanf("%*s%d%d", &x[i], &y[i]);
    }
    int last = bits[N];
    double dp[1 << 16];
    dp[0] = 0;
    for (int state = 1; state < last; state++) {
      bool found = false;
      for (int i = 0; bits[i] < state; i++) {
        for (int j = i + 1; bits[j] < state; j++) {
          if (state & bits[i] && state & bits[j]) {
            double sum = dp[state ^ bits[i] ^ bits[j]] + dis(x[i], y[i], x[j], y[j]);
            dp[state] = min(found ? dp[state] : 2e9, sum);
            found = true;
          }
        }
      }
    }
    printf("Case %d: %.2lf\n", C++, dp[last - 1]);
  }
  return 0;
}

沒有留言:

張貼留言