本题：最短路变形——最大边的最小值

最短路问题Dijkstra算法，题意：
给出两只青蛙、以及其他石头的坐标，需要求出可以到达另一只青蛙的所有路径中，青蛙跳跃距离的最小值
（每一种路径中 青蛙的跳跃距离又是不同的，需要看这条路径中需要跳跃的最长距离）

Input：
输入将包含一个或多个测试用例。每个测试用例的第一行将包含石头数量n（2<=n<=200）。下n行各包含两个整数Xi，Yi（0＜＝Xi，Yi＝1000），表示石头的坐标i。石头1是弗莱迪的石头，石头2是菲奥娜的石头，其他的N-2石头是空的。每个测试用例后面都有一个空白行。对于n，输入以0终止。

Output:
对于每个测试用例，打印一行“Scenario_x”和一行“Frog Distance=y”，其中x替换为测试用例编号（从1开始编号），y替换为适当的实数，打印为三位小数。在每个测试用例之后，甚至在最后一个测试用例之后，都放一个空白行。

• 法一：Floyed
  先跑一遍floyed，获得任意两点间的最短路径，接下来便是重点：改造松弛方程！
对于新加的点i->k，k->j，需要取最大值（最大值才是这条路径上青蛙所需要的最小跳跃距离），而对于点i到点j，则需要取最小值（此时的最小值，才是题目需要求得的值）
  由于给出坐标时第一个和第二个坐标即为两个青蛙的坐标，所以Map[1][2]里保存的即为答案 ps：注意下标从1开始

#include<iostream>
#include<string>
#include<cmath>
#include<ctype.h>
#include<memory.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<iomanip>
#include<set>
#include<list>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
const int maxn = 300;
int Cnt = 0;
int n;
struct jgt
{double x, y;
};
jgt a[maxn];
double Map[maxn][maxn];
double pow2(double x)
{return x * x;
}
int main()
{while (cin >> n){if (n == 0)	break;memset(a, 0, sizeof(a));memset(Map, 0, sizeof(Map));for (int i = 1; i <= n; i++)cin >> a[i].x >> a[i].y;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)Map[i][j] = sqrt(pow2(a[i].x - a[j].x) + pow2(a[i].y - a[j].y));for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)Map[i][j] = min(Map[i][j], max(Map[i][k], Map[k][j]));cout << "Scenario #" << ++Cnt << endl;cout << "Frog Distance = ";printf("%.3f", Map[1][2]);cout << endl << endl;}return 0;
}

• 法二：Dijkstra
改造松弛方程的方法同floyed，其他的代码为dijkstra模板

#include<iostream>
#include<string>
#include<cmath>
#include<ctype.h>
#include<memory.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<iomanip>
#include<set>
#include<list>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
double pow2(double x)
{return x * x;
}
int Cnt = 0;
int n;
const int maxn = 300;
const int INF = 999999;
struct jgt
{double x, y;
};
jgt a[maxn];
double Map[maxn][maxn];
bool vis[maxn];
double dis[maxn];
void dijkstra(int u)
{/*for (int i = 1; i <= n; i++)dis[i] = INF;dis[u] = 0;*/for (int i = 1; i <= n; i++)dis[i] = Map[i][u];vis[u] = 0;for (int i = 1; i <= n; i++){int pos = -1, minn = INF;for (int j = 1; j <= n; j++)if (vis[j] != 1 && dis[j] < minn)//要求的就是最小值，所以{minn = dis[j];pos = j;}if (pos != -1)vis[pos] = 1;for (int j = 1; j <= n; j++){dis[j] = min(dis[j], max(dis[pos], Map[pos][j]));}}}int main()
{while (cin >> n){if (n == 0) break;memset(a, 0, sizeof(a));memset(Map, 0, sizeof(Map));memset(vis, 0, sizeof(vis));memset(dis, 0, sizeof(dis));for (int i = 1; i <= n; i++)cin >> a[i].x >> a[i].y;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)Map[i][j] = sqrt(pow2(a[i].x - a[j].x) + pow2(a[i].y - a[j].y));dijkstra(1);//石头1出发到石头2，dijkstra(1)，输出dis(2)cout << "Scenario #" << ++Cnt << endl;cout << "Frog Distance = ";printf("%.3f", dis[2]);cout << endl << endl;}return 0;
}

最短路变形——最小边的最大值

poj2263