AcWing1125 牛的旅行（floyd）

#include
#includestring>
#include
#include#define x first
#define y second
using namespace std;
typedef pairdouble,double> pll;
const int N=200;
const double inf=1e20;
double d[N][N];
double maxd[N];
string s[N];
int n;
pll q[N];
double get(int i,int j){
    double a=q[i].x-q[j].x;
    double b=q[i].y-q[j].y;
    return  sqrt(a*a+b*b);
}
int main(){
    cin>>n;
    int i;
    for(i=1;i){
        cin>>q[i].x>>q[i].y;
    }
    for(i=1;i){
        cin>>s[i];
    }
    int j;
    for (int i =1; i  )
        for (int j = 1; j  ){
            if(i==j) continue;
            if (s[i][j-1] == ‘1‘) d[i][j] = get(i, j);
            else d[i][j] = inf;
        }
            
    for(int k=1;k){
        for(i=1;i){
            for(j=1;j){
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
    double r1=0;
    for(i=1;i){
        for(j=1;j){
            if(d[i][j]2)
            maxd[i]=max(maxd[i],d[i][j]);
        }
        r1=max(r1,maxd[i]);
    }
    double r2=inf;
    for(i=1;i){
        for(j=1;j){
            if(d[i][j]>inf/2){
                r2=min(r2,maxd[i]+maxd[j]+get(i,j));
            }
        }
    }
    printf("%.6f\n",max(r1,r2));
}