全程double精度就能过了 间接0距离不用管 prim自动连起来的
G++交的话只能用%f输出 C++的话加不加l都可以 (这么说以后用%f肯定不会错咯)
不过我不懂为什么他们的空间时间差了好多倍...
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 0x3F3F3F3F
using namespace std; struct Node{double x, y, z, r;}node[]; typedef pair<double, int> pdi;
struct cmp{
bool operator () (const pdi a, const pdi b){
return a.first > b.first;
}
}; double val[][]; double nodeDist(Node a, Node b){
return max(0.0, sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)
+ (a.z-b.z)*(a.z-b.z)) - a.r - b.r);
} double prim(int n, int s)
{
double ans = , dist[];
bool vis[];
memset(vis, false, sizeof vis);
priority_queue<pdi, vector<pdi>, cmp> q; for(int i = ; i <= n; i++){
dist[i] = val[s][i];
q.push(make_pair(dist[i], i));
}
vis[s] = true;
while(!q.empty()){
pdi u = q.top();
q.pop();
if(vis[u.second]) continue;
vis[u.second] = true;
ans += u.first;
for(int i = ; i <= n; i++){
if(!vis[i] && dist[i] > val[u.second][i]){
dist[i] = val[u.second][i];
q.push(make_pair(dist[i], i));
}
}
}
return ans;
} int main()
{
int n;
while(scanf("%d", &n), n){
for(int i = ; i <= n; i++){
scanf("%lf%lf%lf%lf", &node[i].x, &node[i].y, &node[i].z, &node[i].r);
for(int j = ; j <= i; j++){
val[i][j] = val[j][i] = nodeDist(node[i], node[j]);
}
}
printf("%.3f\n", prim(n, ));
}
return ;
}