2012年8月20日

UVa 10034 - Freckles


#include <stdio.h>
#include <math.h>

typedef struct {
  double x, y;
} Point;

int main() {
  int i, j, n, t;
  scanf("%d", &t);
  while (t--) {
    Point p[150];
    int visit[150] = {0};
    double x, y, w[150][150], d[150], ans = 0;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
      d[i] = 2e9;
    d[0] = 0;
    parent[0] = 0;
    for (i = 0; i < n; i++)
      scanf("%lf%lf", &p[i].x, &p[i].y);
    for (i = 0; i < n; i++)
      for (j = 0; j < n; j++)
        w[i][j] = sqrt(pow((p[i].x - p[j].x), 2) + pow(p[i].y - p[j].y, 2));
    for (i = 0; i < n; i++) {
      int a = -1, b = -1, min = 2e9;
      for (j = 0; j < n; j++)
        if (!visit[j] && d[j] < min) {
          a = j;
          min = d[j];
        }
        if (a == -1) break;
        visit[a] = 1;

        for (b = 0; b < n; b++)
          if (!visit[b] && w[a][b] < d[b]) d[b] = w[a][b];
    }
    for (i = 0; i < n; i++)
      ans += d[i];
    printf("%.2lf\n", ans);
    if (t)
      puts("");
  }
  return 0;
}

沒有留言:

張貼留言