Floyd算法

一个求图中各个点之间最短距离的算法

// 洛谷某道题的题解
#include <cstdio>
#include <cmath>
#include <queue>
#include <utility>
#define FOR(i,a,b) for(int i=a,__endi=b;i<__endi;i++)
using namespace std;
typedef long double real;
bool link[155][155];
real dis[155][155],maxdis[155],d_before;
const real inf=HUGE_VALL;
int n;
typedef pair<int,int> point;
point farms[155];
char tmp[155];
real disEuclid(point a,point b)
    {return hypot(a.first-b.first,a.second-b.second);}
int main(){
#ifndef ONLINE_JUDGE
    freopen("C:\\Users\\dell\\Downloads\\P1522_7.in","r",stdin);
#endif // ONLINE_JUDGE
    scanf("%d",&n);
    FOR(i,0,n)
        scanf("%d %d",&farms[i].first,&farms[i].second);
    FOR(i,0,n){
        scanf("%s",tmp);
        FOR(j,0,n){
            link[i][j]=(tmp[j]=='1');
            dis[i][j]=link[i][j]?disEuclid(farms[i],farms[j]):inf;
            if(i==j)dis[i][j]=0;
        }
    }
    FOR(k,0,n)
        FOR(i,0,n)
            FOR(j,0,n)
                if( dis[i][j]>dis[i][k]+dis[j][k]){
                    dis[i][j]=dis[i][k]+dis[j][k];
                    link[i][j]=true;
                }
    FOR(i,0,n){
        FOR(j,0,n)
            if( maxdis[i]<dis[i][j]&&link[i][j])
                maxdis[i]=dis[i][j];
        if( d_before<maxdis[i])
            d_before=maxdis[i];
    }
    real res=inf;
    FOR(i,0,n){
        FOR(j,0,i){
            if(!link[i][j]){
                real disij=disEuclid(farms[i],farms[j]);
                if( res>maxdis[i]+disij+maxdis[j])
                    res=maxdis[i]+disij+maxdis[j];
            }
        }
    }
    if( res<d_before)
        res=d_before;
    printf("%.6Lf",res);
    return 0;
}