首页 > 代码库 > poj2253

poj2253

受此文启发,dijskstra的改动:http://blog.csdn.net/wangjian8006/article/details/7871812

 

#include<stdio.h>
#include<string.h>
#include<math.h>
#define max(a,b) (a>b?a:b)
double d[201];
typedef struct
{
	int x,y;
}n1;
n1 point[201];
double distance(n1 a,n1 b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));  
}
void dijskstra(int n)
{
	double min;
	int vis[201],v,i;
	memset(vis,0,sizeof(vis));
	for(i=2;i<=n;i++)
	d[i]=1e10;

	d[1]=0;
	d[1]=1;

	while(1)
	{
		min=1e10;
		for(i=1;i<=n;i++)
		{
			if(vis[i]==0&&min>d[i])
			{
				v=i;
				min=d[i];
			}
		}
		if(v==2)
		return;
		vis[v]=1;
		for(i=1;i<=n;i++)
		{
			if(vis[i]==0&&d[i]>max(d[v],distance(point[i],point[v])))
			d[i]=max(d[v],distance(point[i],point[v]));
		}
	}
}
int main()
{
	int n,i,exp;
	exp=0;
	while(scanf("%d",&n)&&n!=0)
	{
		exp++;
		for(i=1;i<=n;i++)
		scanf("%d%d",&point[i].x,&point[i].y);
		dijskstra(n);
		printf("Scenario #%d\n",exp);
		printf("Frog Distance = %.3lf\n\n",d[2]);
	}
	return 0;
}


note:为了能用结构变量做形参,不能用c++里的结构体规则,至今不知为何……求高人指点