题意简述

湖中有N（2<=N<=200）块石头，标号从1到N。青蛙1在石头1上，青蛙2在石头2上。给定所有的石头坐标。青蛙1试图从石头1到石头2来找青蛙2，它可以经由任意石头组成的路径。在所有可能路径中找出一条路径，使其中最长的一步的长度小于其他路径中最长的一步的长度。

本题可以化简为，点1与点2间存在若干条路径，每条路径中都存在最长的一条边。找出一条路径使得该路径最长边的长度小于其他任意路径最长边。

 算法分析

本题的解法之一是Dijkstra的变形。

初看似乎很难把这道题与单源最短路联系在一起。但我们可以做以下分析：

Dijkstra的贪心思想是基于这样一种前提：

设A→P1→P2→P3→B是A到B的最短路，则其中任意一部分亦是最短路。例如P1→P2→P3必然是P1到P3的最短路。证明很简单。假设P1到P3存在一条更短的路，则A到B便可通过该路获得一条更短的路，与题设“A→P1→P2→P3→B是A到B的最短路”矛盾。

由此便得到了Dijkstra的松弛方程：

枚举u。if (d[v]>d[u]+w(u,v)) then d[v]←d[u]+w(u,v)

其中d为源到点最短路长度。u为中转节点。w为u到v的最短路长度。

这是否能和本题的求解过程等同呢？

对于本题，易得两点间最长边最短的路径可能不唯一。但题目只关心点1到点2所有路径中最短的最长边的长度，并不关心具体路径。所以我们在求解过程中，可以人为定义所求路径满足以下条件：

设A→P1→P2→P3→B是我们想要求得的路径，则它满足其中任意一部分亦满足最长边最短。例如P1→P2→P3亦是所有P1到P3路径中最长边最短的。

这样一来，本题的求解，也满足了与Dijkstra相似的贪心过程。它的松弛方程为：

枚举j。if(dis[j]>max(dis[k],map[k][j])) then dis[j]=max(dis[k],map[k][j])

它的意思是，枚举所有中间点k，源到j的目标路径的最长边，要么在源到k这段，要么在k到j这段。

这样，我们便把Dijkstra算法移植到了本题的求解中。除了松弛方程不同，其他部分均与Dijkstra类似。这里不再赘述。

网上的解题报告说这题还可以用最小生成树，日后补充。

Problem Status: AC。时间16ms，内存680k

程序样例

#include<stdio.h>
#include<math.h>

double max(double a, double b) {
  return a > b ? a : b;
}

double frog(int n, int a[][2]) {
  double dis[200], map[200][200], t1, t2, vis[200] = {
    0
  }, min;
  int i, j, k;
  for (i = 0; i < n; i++) {
    dis[i] = 999999;
    for (j = 0; j < n; j++) map[i][j] = 999999;
  }
  for (i = 0; i < n - 1; i++)
    for (j = i + 1; j < n; j++) {
      t1 = (a[i][0] - a[j][0]) * (a[i][0] - a[j][0]) * 1.0;
      t2 = (a[i][1] - a[j][1]) * (a[i][1] - a[j][1]) * 1.0;
      map[i][j] = map[j][i] = sqrt(t1 + t2);
    }
  for (i = 1; i < n; i++) dis[i] = map[0][i];
  vis[0] = 1;
  dis[0] = 0;
  for (i = 1; i < n; i++) {
    min = 999999;
    for (j = 0; j < n; j++)
      if ((min > dis[j]) && (vis[j] == 0)) {
        min = dis[j];
        k = j;
      }
    vis[k] = 1;
    for (j = 0; j < n; j++)
      if ((map[k][j] != 999999) && (!vis[j]) && (dis[j] > max(dis[k], map[k][j])))
        dis[j] = max(dis[k], map[k][j]);
  }
  return dis[1];
}

int main() {
  int x = 1, n, i, a[200][2];
  double ans;
  scanf("%d", & n);
  while (n != 0) {
    for (i = 0; i < n; i++)
      scanf("%d%d", & a[i][0], & a[i][1]);
    ans = frog(n, a);
    printf("Scenario #%d\n", x);
    printf("Frog Distance = %.3fn\n", ans);
    x++;
    scanf("%d", & n);
  }
  return 0;
}