POJ 2253-最短路-floyd

原题链接

题意

青蛙从一号点，想跳到二号点，然而距离可能特别大，青蛙可能一次跳不了太远，
所以需要借其他点，从而缩短单次需要跳的最长距离
例如，a->b等于10，如果直接跳，那么单次跳的距离为10
如果有a->c=5,c->b=5，那么先到c，再到b，单次跳的距离就是5

思路

使用floyd，然而不是求最短路，而是求能到单次跳所需要的最大距离
即所有路径中的最大值
因此，原本floyd状态表达式是

g[i][j]=min(g[i][j],g[i][k]+g[k][j]//求总路径之和的最短距离

应改成

g[i][j]=min(g[i][j],max(g[i][k],g[k][j]));//求从i直接到j，是否能通过k点，缩短单次跳所需要最大长度

max(g[i][k],g[k][j])是求出i->k和k->j两条路径的最大单次跳的距离
min(g[i][j],max(g[i][k],g[k][j]));则求出是否被替换，从而求出更小的值

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std;

const int N=220,inf=0x3f3f3f3f;
typedef double dl;
typedef pair<int,int > PII;

dl g[N][N]; 
PII p[N];
int n;

//求x跟y之间的直接距离 
dl find(int x,int y){
    double a=p[x].first-p[y].first;
    double b=p[x].second-p[y].second;
    return sqrt(a*a+b*b);
}
int main()
{
    int num=0;
    while(cin>>n,n){
        //接收所有点的坐标 
        for(int i=1;i<=n;i++) cin>>p[i].first>>p[i].second;
        
        //一次求出每两个点之间的距离 
        for(int i=1;i<=n;i++){
            //因为i到j跟j到i的距离是一定的
            //所以遍历的时候，可以直接遍历矩阵的右上角即可 
            for(int j=i+1;j<=n;j++){
                g[i][j]=g[j][i]=find(i,j);
            }
        }
        
        //floyd求出最小单次跳的距离 
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    g[i][j]=min(g[i][j],max(g[i][k],g[k][j]));
                }
            }
        }
        if(num) cout<<endl;
        printf("Scenario #%d\nFrog Distance = %.3f\n",++num,g[1][2]);
    }
    return 0;
}