题目链接: http://poj.org/problem?id=2031
题意:现给定一些细胞的坐标以及它们的半径,求它们彼此联通的最短路径是多少。实则是最小生成树。
////特别心塞,G++提交就错,C++提交就A,害我找错好半天。。。
*** 百度说G++ 和C++ 的区别在于 %lf 和 %f 由于这道题里面涉及到了 所以才会WA
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<algorithm> #include<queue> #include<iostream> using namespace std; #define maxn 10000 double maps[maxn][maxn]; double x[maxn], y[maxn], z[maxn], r[maxn], dist[maxn]; int v[maxn]; int n; void Init() { int i, j; for(i=1; i<=n; i++) for(j=1; j<=n; j++) if(i==j) maps[i][j] = 0; else maps[i][j]=maps[j][i]= 10000000 ; } double Dij() { memset(dist, 0, sizeof(dist)); memset(v, 0, sizeof(v)); for(int i=1; i<=n; i++) dist[i] = maps[1][i]; v[1] = 1; double sum = 0; for(int i=1; i<n; i++) { int index; double mins=10000000; for(int j=1; j<=n; j++) { if(!v[j] && dist[j] < mins) { index = j; mins = dist[j]; } } if(mins == 10000000) return 0; sum += mins; v[index] = 1; for(int j=1; j<=n; j++) { if(!v[j] && dist[j] >= maps[index][j]) { dist[j]= maps[index][j]; } } } return sum; } int main() { while(scanf("%d", &n), n) { for(int i=1; i<=n; i++) scanf("%lf %lf %lf %lf", &x[i], &y[i], &z[i], &r[i]); Init(); for(int i=1; i<n; i++) { for(int j=i+1; j<=n; j++) { double d=sqrt((x[j]-x[i])*(x[j]-x[i])+(y[j] - y[i])*(y[j] - y[i])+(z[j]-z[i])*(z[j]-z[i])) ; double p = r[i] + r[j]; if(d <= p) { maps[i][j]=maps[j][i]=0; continue; } maps[i][j] = maps[j][i] = min(maps[i][j], d-p); } } double ans = Dij(); printf("%.3lf ",ans); } return 0; }