现在的位置: 首页 > 综合 > 正文

杭电1162 Eddy’s picture

2013年04月26日 ⁄ 综合 ⁄ 共 1450字 ⁄ 字号 评论关闭

/*********************************
 *    日期:2011-3-8
 *    作者:SJF
 *    题号:杭电1162
 *    题目:Eddy's picture
 *    结果:AC
 *    总结:
**********************************/
#include <stdio.h>
#include <string.h>
#include <math.h>
int n;
double distance[101][101];
typedef struct
{
    double x;
    double y;
    int visit;
}Point;
Point point[101];
void Distance()
{
    int i,j,snum=1;//s[snum]表示已找出点的编号,snum找出点的个数
    int s[101],minnum;
    double min,len=0;
    s[0]=0;
    point[0].visit=1;
    while(snum!=n+1)
    {
        min=0;
        for(i=0;i<snum;i++)
        {
            for(j=0;j<n;j++)
            {
                if(point[j].visit==0)//该点没找过
                {
                    if(distance[s[i]][j]<min||min==0)
                    {
                        min=distance[s[i]][j];
                        minnum=j;
                    }
                }
            }
        }
        s[snum]=minnum;
        point[minnum].visit=1;
        snum++;
        len+=min;
    }
    printf("%.2lf\n",len);
}
int main()
{
    int i,j;
    double k;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
        {
            scanf("%lf %lf",&point[i].x,&point[i].y);
            point[i].visit=0;
        }
        memset(distance,0,sizeof(distance));
        for(i=0;i<n;i++)
        {
            for(j=i+1;j<n;j++)
            {
                k=sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y));
                distance[j][i]=k;
                distance[i][j]=k;
            }
        }
        Distance();
    }
    return 0;
}

 

抱歉!评论已关闭.