#include<iostream>
#include<cmath>

using namespace std;
 
#define MAX 202
#define INF 10000000
#define max(a, b) a > b ? a : b

struct P
{
	double x, y;
}; P point[MAX];

double G[MAX][MAX];

double distance(P e1, P e2)
{
	return sqrt((e1.x - e2.x) * (e1.x - e2.x) + (e1.y - e2.y) * (e1.y - e2.y));
}

double Dij(int n,int s,int t)
{
	int i,j,w,mark[MAX];
	double minc,d[MAX];
	for (i=1;i<=n;i++) mark[i]=0;
	for (i=1;i<=n;i++)
		d[i]=G[s][i];
	mark[s]=1;
	d[s]=0;
	for (i=2;i<=n;i++)
	{
		minc=INF;
		w=0;
		for (j=1;j<=n;j++)
			if ((mark[j]==0)&&(minc>=d[j])) {
				minc=d[j];
				w=j;
			}
		mark[w]=1;
		for (j=1;j<=n;j++)
			if ((mark[j]==0)&&(G[w][j]!=INF)&&(d[j]>d[w] && d[j]>G[w][j]))
				d[j]=max(d[w],G[w][j]);
	}
	return d[t];
}

int main()
{
	int n;
	int i, j;
	int gg = 0;
	while(scanf("%d", &n) && n) {
		for(i = 1; i <= n; i ++)
			for(j = 1; j <= i; j ++)
				if(i == j)
					G[i][j] = 0;
				else
					G[i][j] = G[j][i] = INF;
		for(i = 1; i <= n; i ++)
			scanf("%lf%lf", &point[i].x, &point[i].y);
		for(i = 1; i <= n; i ++)
			for(j = 1; j < i; j ++)
				G[i][j] = G[j][i] = distance(point[i], point[j]);

		printf("Scenario #%d\nFrog Distance = ", ++ gg);
		printf("%.3lf\n\n", Dij(n, 1, 2));
	}

	return 0;
}

• 前者AC 后者CE - -# (274) allen4053040allen 2010-06-08 11:11:50
  • 问题出在名字- -# (300) allen4053040allen 2010-06-09 08:44:57
    • Re:问题出在名字- -# (25) Weizengke 2012-03-20 16:58:58