Floyd算法

一個求圖中各個點之間最短距離的算法

<source lang="cpp"> // 洛谷某道題的題解

1. include <cstdio>
2. include <cmath>
3. include <queue>
4. include <utility>
5. 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(){

1. ifndef ONLINE_JUDGE

   freopen("C:\\Users\\dell\\Downloads\\P1522_7.in","r",stdin);

1. 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;

} </source>