学步园

prim水题，别被3D吓到。

注意相交情况和浮点数的比较就行了。

//296K 32ms
#include <iostream>
#include <cmath>
using namespace std;

#define INF 10000.000
#define SIZE 102
#define EPS 1e-10
int n;
double graph[SIZE][SIZE], dist[SIZE];
bool visit[SIZE];

struct Node
{
	double x, y, z, r;
} node[SIZE];

double cal_dis(Node *a, Node *b)
{
	double ans = sqrt(pow(a->x-b->x,2.0)+pow(a->y-b->y,2.0)+pow(a->z-b->z,2.0))-a->r-b->r;
	if(fabs(ans) < EPS)
		return 0.0;
	else return ans > 0.0 ? ans : 0.0;
}

double Prim()
{
	double min_value, tmp;
    int i, j, curr;

	memset(visit, false, sizeof(visit));
	for(i = 1; i < n; i++)
		dist[i] = INF;
	dist[0] = 0.000;
    min_value = 0.000;

	for(j = 0; j < n; j++)
	{
         tmp = INF;
		 curr = -1;
		 for(i = 0; i < n; i++)
		 {
			 if(!visit[i] && dist[i] < tmp)
			 {
				 tmp = dist[i];
				 curr = i;
			 }
		 }

		 if(curr == -1)
			 break;
		 min_value += tmp;
		 visit[curr] = true;
		 for(i = 0; i < n; i++)
			 if(!visit[i] && graph[curr][i] < dist[i])
				 dist[i] = graph[curr][i];
	}
    return min_value;
}
int main()
{
	int i, j;
    double x, y, z, r;
//	freopen("a.txt","r",stdin);
	while(scanf("%d", &n) && n)
	{
        for(i = 0; i < n; i++)
        {
			scanf("%lf%lf%lf%lf", &x, &y, &z, &r);
			node[i].x = x;
			node[i].y = y;
			node[i].z = z;
			node[i].r = r;
		}
		for(i = 0; i < n; i++)
			for(j = i; j < n; j++)
			{
				if(i == j)
					graph[i][j] = 0.000;
				else
				{
					graph[i][j] = cal_dis(&node[i], &node[j]);
					graph[j][i] = graph[i][j];
				}
			}
        printf("%.3lf\n", Prim());
	}
	return 0;
}