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

prime算法!付一下代码!仅供参考!!!

Posted by chenxuan123456789 at 2012-09-11 22:19:42 on Problem 3625
#include <stdio.h>
#include <string.h>
#include <math.h>
double road[1010][1010];
double dist[1010];
int visit[1010];
struct node
{
	double x,y;
};
struct node data[1010];
int main()
{
	int n,m,i,j,rec;
	double d,sum,max;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		for(i=1;i<=n;i++)
		scanf("%lf %lf",&data[i].x,&data[i].y);
		memset(road,0,sizeof(road));
		for(i=1;i<=n;i++)
		{
			for(j=i+1;j<=n;j++)
			{
				d=sqrt((data[i].x-data[j].x)*(data[i].x-data[j].x)+(data[i].y-data[j].y)*(data[i].y-data[j].y));
				road[i][j]=d;
				road[j][i]=road[i][j];
			}
		}
		while(m--)
		{
			scanf("%d %d",&i,&j);
			road[i][j]=0;
			road[j][i]=0;
		}
		memset(visit,0,sizeof(visit));
		for(i=1;i<=n;i++)
		dist[i]=road[1][i];
		visit[1]=1;
		sum=0.0;
		for(i=1;i<n;i++)
		{
			max=10000000.0;
			rec=-1;
			for(j=1;j<=n;j++)
				if(!visit[j]&&dist[j]<max)
				{
					max=dist[j];
					rec=j;
				}
				sum+=max;
				visit[rec]=1;
				for(j=1;j<=n;j++)
					if(!visit[j]&&road[rec][j]<dist[j])
						dist[j]=road[rec][j];
		}
		printf("%.2lf\n",sum);
	}
	return 1;
}



			




Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator