1127 Building a Space Station
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string.h>
#include<queue>
struct E{
int no;
double cost;
bool operator<(const E& e)const{
return cost>e.cost;
}
};
void calc(int n){
double xs[101],ys[101],zs[101],rs[101],len,ans=0;
double lens[101][101];
double mymax=1000000000;
for(int i=0;i<n;i++){
scanf("%lf %lf %lf %lf",&xs[i],&ys[i],&zs[i],&rs[i]);
lens[i][i]=mymax;
for(int j=0;j<i;j++){
len=sqrt(pow(xs[i]-xs[j],2)+pow(ys[i]-ys[j],2)+pow(zs[i]-zs[j],2))-rs[i]-rs[j];
if(len<=0)len=0;
lens[i][j]=lens[j][i]=len;
}
}
bool conOKs[101];
memset(conOKs,false,sizeof(conOKs));
E e1;
int no;
e1.no=0;
e1.cost=0;
std::priority_queue<E> qu;
qu.push(e1);
while(!qu.empty()){
e1=qu.top();
qu.pop();
no=e1.no;
if(conOKs[no]==true)continue;
conOKs[no]=true;
ans+=e1.cost;
for(int i=0;i<n;i++){
if(i==no||conOKs[i]==true)continue;
e1.no=i;
e1.cost=lens[no][i];
qu.push(e1);
}
}
printf("%.3lf\n",ans);
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
calc(n);
}
}
最終更新:2012年07月14日 20:02