Topic: Give the number of spherical space stations N, and the three-dimensional coordinates x,y,z and radius r of each space station. Find the minimum cost of connecting all space stations (cost is equal to the distance between space stations). If contacting, including, or intersecting, there is no need to build bridges.

Idea: It's also a minimal spanning tree topic. We first record the information of each space station, and then connect all space stations in two. If we touch, include, or intersect, we set cost to 1, otherwise we use the sum of distance radius.

Each space station is represented by a label and recorded in the forward star. Use the prim algorithm to find the minimum spanning tree.

One more thing to note is that the final output is to use% f instead of% lf in G++.

Complete code;

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1000;
const int maxm = 1e5;
int n,m;
double ans;
typedef pair<double,int> pii;
struct Egde{
    int u,v,next;
    double w;
}edge[maxm];
struct node{
    double x,y,z,r;
}space[maxn];
struct cmp{
    bool operator () (pii a, pii b){
        return a.first > b.first;
    }
};
int head[maxn];
int vis[maxn];
double dist[maxn];
int top;
void init(){
    memset(head,-1,sizeof(head));
    memset(vis,0,sizeof(vis));
    memset(dist,-1,sizeof(dist));
    top = 0;
    ans = 0;
}
void add(int u,int v,double w){
    int i;//Updating the Minimum Edge Weight 
    for(i=head[u]; ~i; i=edge[i].next){
        if(edge[i].v == v){
            if(edge[i].w > w) edge[i].w = w;
            return ;
        }    
    }
    edge[top].u = u;
    edge[top].v = v;
    edge[top].w = w;
    edge[top].next = head[u];
    head[u] = top++;
}
void prim(int s){
    int i;
    priority_queue<pii,vector<pii>, cmp>q;
    vis[s] = 1;
    dist[s] = 0;
    for(i = head[s];~i;i = edge[i].next){
        int v = edge[i].v;
        dist[v] = edge[i].w;
        q.push(make_pair(dist[v],v));
    }
    while(!q.empty()){
        pii t = q.top();
        q.pop();
        if(vis[t.second]) continue;
        ans += t.first;
        vis[t.second] = 1;
        
        for(i = head[t.second]; ~i;i = edge[i].next){
        int v = edge[i].v;
        if(!vis[v]&&(dist[v]>edge[i].w)||dist[v] == -1){
            dist[v] = edge[i].w;
            q.push(make_pair(dist[v],v));
            }
        }        
    }
    
}
double getDist(int i,int j){
    double sX = (space[i].x-space[j].x)*(space[i].x-space[j].x);
    double sY = (space[i].y-space[j].y)*(space[i].y-space[j].y);
    double sZ = (space[i].z-space[j].z)*(space[i].z-space[j].z);
    double dis =  sqrt(sX+sY+sZ);
    if(dis<=(space[i].r+space[j].r)) return 0.00;
    else return dis-(space[i].r+space[j].r); 
}
int main(){
    while(cin>>n&&n){
//        cin>>m;
        init();
        for(int i=0; i<n;i++){
            cin>>space[i].x>>space[i].y>>space[i].z>>space[i].r;
        }
        for(int i=0; i<n;i++){
            for(int j=0;j<n;j++){
                if(i==j) continue;
                add(i,j,getDist(i,j));
                add(j,i,getDist(j,i));
            }
        } 
        prim(0); 

        printf("%.3f\n",ans);//Note: In G++, precision is output with% f, and if output with% lf, wa will occur.
    }
}