弗洛伊德算法：
（1）弗洛伊德算法求出任意两点间的最短路，然后求出每个点到所有可到达点的最大距离，记为 m[i]
（2）r1=max( m [ i ] )
（3）枚举不联通的两个点 i , j，把它们联通，则新的直径是m[i]+m[j]+dist(i,j)
（4）r2=min( m[i] + m[j] + dist( i , j ) )
（5）re=max ( r1 , r2 )
代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> using namespace std; int n; char ch; int a[151][3]; double f[151][151],maxt=1e12,minx=1e20,temp,m[151]; double dist(int x,int y) { return sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2)); } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i][1]>>a[i][2]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { cin>>ch; if(ch==‘1‘) f[i][j]=dist(i,j); else f[i][j]=maxt; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=k&&i!=j&&j!=k) if(f[i][k]<maxt-1&&f[k][j]<maxt-1) //确保连通 if(f[i][j]>f[i][k]+f[k][j]) f[i][j]=f[i][k]+f[k][j]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(f[i][j]<maxt-1&&m[i]<f[i][j]) m[i]=f[i][j]; //(1) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j&&f[i][j]>maxt-1) { temp=dist(i,j); if(minx>m[i]+m[j]+temp) minx=m[i]+m[j]+temp; } //(4) for(int i=1;i<=n;i++) if(m[i]>minx) //(2)(5) minx=m[i]; printf("%.6lf",minx); return 0; }
原文：https://www.cnblogs.com/xiaoyezi-wink/p/10745523.html