ACdream 孟竹要减肥？（prim）

刚开始题目看错了，一直wa，输入的坐标是浮点型。。。。。。。
听了队友的，才知道prim算法只需要枚举到sqrt（n）就完全足够了，发现sqrt（n）好多地方用的到。
View Code
 1 #include<stdio.h>
 2 #include<math.h>
 3  
 4 const int MAXN=510;
 5 const int INF=0x7fffffff;
 6 struct Node
 7 {
 8     double x,y;
 9 } node[MAXN];
10  
11 double temp;
12 double dist[MAXN];//dist[i]表示i向外延伸的最短边长
13 double map[MAXN][MAXN];//储存a->b之间的边权值
14 int pre[MAXN];//pre[i]记录i的父节点
15 int n,m;
16  
17 double _dist(Node a,Node b)
18 {
19     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
20 }
21  
22 void Prim(int s)
23 {
24     int i,j,k;
25     double min;
26     bool p[MAXN];//区分Va集合和Vb集合
27     for(i=1; i<=n; i++)
28     {
29         p[i]=false;
30         dist[i]=map[s][i];
31         pre[i]=s;
32     }
33     dist[s]=0;
34     p[s]=true;
35     for(i=1; i<=n-1; i++) //循环n-1次，每次加入一个点
36     {
37         min=INF;
38         k=0;
39         for(j=1; j<=n; j++)
40         {
41             //若j还在Vb集合中，并且j的路径可以再小点(找当前i点所对应的最短权值)
42             if(!p[j] && dist[j]<min)
43             {
44                 min=dist[j];
45                 k=j;
46             }
47         }
48         if(k==0) return ;//如果没有点可以扩展，即图G不连通，返回
49         if(temp<dist[k]) temp=dist[k];
50         if(i==m) return ;
51         p[k]=true;//将点k移到Va集合
52         for(j=1; j<=n; j++) //更新相邻k相邻的点（有些dist依旧记录着以前Va结点中相邻的点）
53         {
54             //对于每个与k相邻的Vb中的点j，更新j距离最近的点及其距离
55             if(!p[j] && map[k][j]!=INF && dist[j]>map[k][j])
56             {
57                 dist[j]=map[k][j];
58                 pre[j]=k;
59             }
60         }
61     }
62 }
63  
64 int main()
65 {
66     int T,i,j;
67     scanf("%d",&T);
68     while(T--)
69     {
70         scanf("%d%d",&n,&m);
71         for(i=1; i<=n; i++)
72         {
73             scanf("%lf%lf",&node[i].x,&node[i].y);
74         }
75         for(i=1; i<=n; i++)
76         {
77             for(j=1; j<=n; j++)
78             {
79                 map[i][j]=_dist(node[i],node[j]);
80             }
81         }
82         double res=INF;
83         for(i=1; i*i<=n; i++)//////
84         {
85             temp=0;
86             Prim(i);
87             if(res>temp) res=temp;
88         }
89         printf("%.4lf\n",res);
90     }
91     return 0;
92 }