1 #include <cstdio> 2 #include <cmath> 3  4 double dis[105][105]; 5 double p[105][2]; //输入坐标点 6 double d[105];  //一点到另一点的距离 7 double vis[105];  //记得该点是否已被访问 8 double len; 9 int n;10 11 //初始化dis[105][105]12 void init()13 {14     int i,j;15     for(i=1; i<=n; i++)16     {17         for(j=1; j<=n; j++)18         {19             dis[i][j]=dis[j][i]=100000000;20         }21         vis[i] = 0;22     }23     len=0.0;24 }25 26 //计算dis[105][105]27 void makedis()28 {29     int i,j;30 31     for(i = 1; i <= n; i++)32         for(j = i; j <= n; j++)33         {34             dis[i][j] = dis[j][i] = sqrt((p[i][0]-p[j][0])*(p[i][0]-p[j][0])+(p[i][1]-p[j][1])*(p[i][1]-p[j][1]));35 36         }37 }38 39 40 //用prim算法求最短距离41 void prim()42 {43     int i,j,k;44     double min;45     for(i = 1; i <= n; i++)46         d[i] = dis[1][i];47     vis[1] = 1;48 49     for( i = 1; i < n; i++)50     {51         min = 0xfffffff;              // 最大值52         for ( j = 1; j <= n; j++)53         {54             if ( d[j] < min && !vis[j])55             {56                 min = d[j];57                 k = j;58             }59         }60         vis[k] = 1;61         len += d[k];62         for(j = 1; j <= n; j++)63         {64             if(!vis[j] && d[j] > dis[k][j])65                 d[j] = dis[k][j];66         }67 68     }69 }70 71 //主函数72 int main()73 {74     int step;75     int i;76     step=0;77     while(scanf("%d",&n) && n)     //以0结束78     {79         step++;              //记录case80 81         if(step!=1)82             printf("\n");83         init();84         for(i = 1; i <= n; i++)85         {86             scanf("%lf%lf",&p[i][0],&p[i][1]);87         }88         makedis();89         prim();90         printf("Case #%d:\n",step);91         printf("The minimal distance is: %.2lf\n",len);92     }93     return 0;94 }