题意：

青蛙想从一个石子跳到另一个石子，中间有很多石子，要求青蛙跳跃距离应为路径中最大的距离，现在要求所有路径中最小的跳跃距离，就是求所有路径中最大距离的最小值。

要点：

可以用最短路径做，用Floyd算法，不断往里加点，只不过这次dis数组表示最大距离的最小值，而用max（map[i][k], map[k][j])）取路径中的最大跳跃距离，这种比较好理解，网上也有很多用dijkstra算法做的，比较难理解还是算了。

15415520

Accepted

504K

110MS

799B

2016-04-20 16:56:10

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;struct node{	int x, y;}a[205];double map[205][205];int main(){	int n,count=1;	while (scanf("%d", &n) && n)	{		for (int i = 1; i <= n; i++)			scanf("%d%d", &a[i].x, &a[i].y);		for (int i = 1; i <= n; i++)			for (int j = 1; j <= n; j++)			{				double x = a[i].x - a[j].x;				double y = a[i].y - a[j].y;				map[i][j] = map[j][i] = sqrt(x*x + y*y);			}		for (int k = 1; k <= n; k++)			for (int i = 1; i <= n; i++)				for (int j = 1; j <= n; j++)					if (map[i][j] > max(map[i][k], map[k][j]))//就是始终求路径中的最大权边，并取最大权边的最小值						map[i][j] = max(map[i][k], map[k][j]);//这里如果用预处理器会失败，中间莫名其妙会算错，也不知道为什么		printf("Scenario #%d\n", count++);		printf("Frog Distance = %.3lf\n\n", map[1][2]);	}	return 0;}