D63 最短路 Floyd 算法 P1522 [USACO2.4] 牛的旅行

// 最短路 Floyd 算法 O(n^3)
#include<bits/stdc++.h>
using namespace std;

#define pdd pair<double,double>
#define x first
#define y second
const int N=155;
const double INF=1e15; //10^5*1.414*150
int n;
pdd q[N];
char g[N][N];
double d[N][N],maxd[N];

double dis(pdd a,pdd b){
  return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main(){
  cin>>n;
  for(int i=0; i<n; i++) cin>>q[i].x>>q[i].y; //n个点的坐标
  for(int i=0; i<n; i++) cin>>g[i]; //图的连通性
  for(int i=0; i<n; i++) //初始化d数组
    for(int j=0; j<n; j++)
      if(g[i][j]=='1') d[i][j]=dis(q[i],q[j]);
      else if(i==j) d[i][j]=0;
      else d[i][j]=INF;
      
  for(int k=0; k<n; k++) //Floyd求最短路
    for(int i=0; i<n; i++)
      for(int j=0; j<n; j++)
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
        
  for(int i=0; i<n; i++) //求每个连通块的直径 maxd
    for(int j=0; j<n; j++)
      if(d[i][j]<INF/2) //如果两点连通，因浮点数精度问题不写==INF
        maxd[i]=max(maxd[i],d[i][j]);
  
  double r1=INF; int a=0,b=0;
  for(int i=0; i<n; i++) //求连边后的直径r1，记录两个块a,b
    for(int j=0; j<n; j++)
      if(d[i][j]>INF/2)  //如果两点不连通
        if(r1>maxd[i]+maxd[j]+dis(q[i],q[j]))
          r1=maxd[i]+maxd[j]+dis(q[i],q[j]),a=i,b=j;
          
  double r2=0,r3=0;
  for(int i=0; i<n; i++) //求a块的直径r2
    if(d[a][i]<INF/2) r2=max(r2,maxd[i]);
  for(int i=0; i<n; i++) //求b块的直径r3
    if(d[i][b]<INF/2) r3=max(r3,maxd[i]);
    
  printf("%.6lf\n",max(r1,max(r2,r3))); //新牧场的直径
}