题意：想给你公青蛙位置，再给你母青蛙位置，然后给你剩余位置，问你怎么走，公青蛙全力跳的的最远距离最小。
思路：这里不是求最短路径，而是要你找一条路，青蛙走这条路时，对他跳远要求最低。这个思想还是挺好迁移的，原来我们用mp[i][j]表示i到j最短路径，那么我们现在用它表示i到j最大步伐，然后每次比较，只要最大步伐比他小，那么我们就走新的路。注意最后是mp[1][2]，一直mp[1][n]没改无限WA。
代码;
#include#include #include #include #include #include #define ll long longusing namespace std;const int maxn = 200+5;const int INF = 0x3f3f3f3f;struct Node{ double x,y;}node[maxn];double mp[maxn][maxn]; //表示i->j的最大步伐int Case = 1;void Floyd(int n){ for(int k = 1;k <= n;k++){ for(int i = 1;i <= n;i++){ for(int j = 1;j <= n;j++){ if(mp[i][j] > max(mp[i][k],mp[k][j])){ //这样走最大步伐比较小 mp[i][j] = mp[j][i]= max(mp[i][k],mp[k][j]); } } } } printf("Scenario #%d\nFrog Distance = %.3lf\n\n",Case++,mp[1][2]);}int main(){ int n,m; while(~scanf("%d",&n) && n){ for(int i = 1;i <= n;i++) scanf("%lf%lf",&node[i].x,&node[i].y); for(int i = 1;i <= n;i++){ for(int j = i + 1;j <= n;j++){ mp[i][j] = mp[j][i] = sqrt((node[i].x - node[j].x)*(node[i].x - node[j].x) + (node[i].y - node[j].y)*(node[i].y - node[j].y)); } } Floyd(n); } return 0;}