Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 我的也是 高手看看！

Posted by 0712105003 at 2010-04-11 18:51:05 on Problem 2031
In Reply To:大牛帮忙看看，为什么C++AC G++WA Posted by:seu_cl at 2009-06-26 13:47:09
```#include <iostream>
#include<stdio.h>
#include<math.h>
#include<memory>
#include<string.h>
using namespace std;
int N;
double x[105],y[105],z[105],r[105];
double dis[105];
int visited[105];
double ans;
double getdis(int i,int j)
{
double t = sqrt((x[i] - x[j]) *(x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) + (z[i] - z[j]) * (z[i] - z[j]));
if(t > r[i] + r[j])return t - r[i] - r[j];
else return 0;
}
void prim()
{
ans = 0.0;
for(int i = 0 ;i < N;i ++)
{
dis[i] = getdis(0,i);
}
memset(visited,0,sizeof(visited));
visited[0] = 1;
for(int i = 1 ; i < N ; i ++)
{
int  u = 0;
double min = 10000.0;
for(int j = 0 ; j < N ;j ++)
{
if(visited[j] == 0 && min > dis[j])
{
min = dis[j];
u = j;
}
}
visited[u] = 1;
ans = ans + min;
for(int j = 0 ; j < N ; j ++)
{
if(visited[j] == 0)
{
double t = getdis(u,j);
if(dis[j] > t)
dis[j] = t;
}
}

}
printf("%.3lf\n",ans);

}
int main()
{
freopen("datain.in","r",stdin);
while(scanf("%d",&N) && N)
{
for(int i = 0;i < N;i ++)
{
scanf("%lf%lf%lf%lf",&x[i],&y[i],&z[i],&r[i]);
}
prim();
}
return 0;
}
```

Followed by: