POJ 2253 Frogger

//变形的dijkstra//核心代码//if( d[j]>max(d[k],map[k][j]))// d[j]=max(d[k],map[k][j]);

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<cmath>
using namespace std;
#define max 999999
struct node
{
	int x,y;
}p[210];
int map[210][210],f[210],d[210];

int com(node a,node b)
{
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int n;

int mx(int a,int b)
{
	return a>b?a:b;
}
void dijkstra()
{
	int i,j,k;
	for(i=1;i<=n;i++)
	{
		d[i]=map[1][i];
		f[i]=0;
	}
	f[1]=1;
	d[1]=0;
	for(i=1;i<=n;i++)
	{
		int min=max;
		k=0;
		for(j=1;j<=n;j++)
			if(!f[j] && d[j]<min)
			{
					min=d[j];
					k=j;
			}
		if(k==0) return ;
		f[k]=1;
		for(j=1;j<=n;j++)
		{
			if(!f[j] && map[k][j]!=max && d[j]>mx(d[k],map[k][j]))
				d[j]=mx(d[k],map[k][j]);
		}
	}
}
int main()
{
	int i,j,k;
	int t=0;
	while(scanf("%d",&n),n)
	{
		t++;
		for(i=1;i<=n;i++)
			scanf("%d%d",&p[i].x,&p[i].y);
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(i==j)
					map[i][j]=0;
				else
					map[i][j]=max;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				map[i][j]=com(p[i],p[j]);
		dijkstra();
		printf("Scenario #%d\n",t);
		printf("Frog Distance = %.3lf\n",sqrt(1.0*d[2]));
		printf("\n");
	}
}




#include<stdio.h>
#include<string.h>
#include<math.h>
#include<cmath>
using namespace std;
#define max 999999
struct node
{
	int x,y;
}p[210];
int map[210][210],f[210],d[210];

int com(node a,node b)
{
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int n;

int mx(int a,int b)
{
	return a>b?a:b;
}
void dijkstra()
{
	int i,j,k;
	for(i=1;i<=n;i++)
	{
		d[i]=map[1][i];
		f[i]=0;
	}
	f[1]=1;
	d[1]=0;
	for(i=1;i<=n;i++)
	{
		int min=max;
		k=0;
		for(j=1;j<=n;j++)
			if(!f[j] && d[j]<min)
			{
					min=d[j];
					k=j;
			}
		if(k==0) return ;
		f[k]=1;
		for(j=1;j<=n;j++)
		{
			if(!f[j] && map[k][j]!=max && d[j]>mx(d[k],map[k][j]))
				d[j]=mx(d[k],map[k][j]);
		}
	}
}
int main()
{
	int i,j,k;
	int t=0;
	while(scanf("%d",&n),n)
	{
		t++;
		for(i=1;i<=n;i++)
			scanf("%d%d",&p[i].x,&p[i].y);
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(i==j)
					map[i][j]=0;
				else
					map[i][j]=max;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				map[i][j]=com(p[i],p[j]);
		dijkstra();
		printf("Scenario #%d\n",t);
		printf("Frog Distance = %.3lf\n",sqrt(1.0*d[2]));
		printf("\n");
	}
}