题目链接：http://poj.org/problem?id=2253
题意：
给出两只青蛙的坐标A、B，和其他的n-2个坐标，任一两个坐标点间都是双向连通的。显然从A到B存在至少一条的通路，每一条通路的元素都是这条通路中前后两个点的距离，这些距离中又有一个最大距离。
现在要求求出所有通路的最大距离，并把这些最大距离作比较，把最小的一个最大距离作为青蛙的最小跳远距离。
思路：
j从1,2，两条路中选取较小者，而1这条路，是s—>k—>j的最大步伐。
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm> using namespace std; #define INF 0x3f3f3f3f struct Point
{
double x;
double y;
} points[]; double maps[][];
bool vis[];
double dis[];
int n; void Dijkstra(int s)
{
memset(vis,false,sizeof(vis)); for(int i=;i<=n;i++)
dis[i] = maps[s][i]; vis[s] = true;
for(int i=;i<n;i++)
{
int k = ,tmp = INF;
for(int j=;j<=n;j++)
{
if(vis[j]) continue;
if(dis[j]<tmp)
{
tmp = dis[j];
k = j;
}
}
vis[k] = true; for(int j=;j<=n;j++)
{
if(vis[j]) continue;
dis[j] = min(dis[j],max(dis[k],maps[k][j]));
}
}
} int main()
{
int cases = ;
while(scanf("%d",&n),n)
{
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
maps[i][j] = INF; for(int i=; i<=n; i++)
scanf("%lf%lf",&points[i].x,&points[i].y); for(int i=; i<=n; i++)
{
for(int j=i+; j<=n; j++)
{
double tx = points[i].x - points[j].x;
double ty = points[i].y - points[j].y;
maps[i][j] = maps[j][i] = sqrt(tx*tx+ty*ty);
}
}
Dijkstra();
printf("Scenario #%d\nFrog Distance = %.3lf\n\n",cases++,dis[]);
}
return ;
}