原题链接

又是
01之间不打空格的输入
又是
我最讨厌的字符串
设计输入格式的人
为什么这么
讨厌空格呢

先跑一遍Floyd
找出哪几个点不在一个牧区内
然后看
连接哪两个点最路径最短
这个题的难度评级
为什么会这么高呢

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;struct nico
{int x,y;
}map[200];double dis[200][200],ans=1e9,m,dism[200];
int n,f[200][200],i,j,k;
char c;int main()
{   scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d%d",&map[i].x,&map[i].y);for(i=1;i<=n;i++)for(j=1;j<=n;j++){cin>>c;f[i][j]=c-'0';  if(f[i][j]==1)dis[i][j]=sqrt((map[i].x-map[j].x)*(map[i].x-map[j].x)+(map[i].y-map[j].y)*(map[i].y-map[j].y));else dis[i][j]=1e9;}for(i=1;i<=n;i++)for(j=1;j<=n;j++)for(k=1;k<=n;k++)if((j!=k&&i!=j&&i!=k)&&(dis[j][i]<1e9&&dis[i][k]<1e9)) dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k]);for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(dis[i][j]<1e9&&i!=j) dism[i]=max(dism[i],dis[i][j]);for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(dis[i][j]==1e9&&i!=j){m=sqrt((map[i].x-map[j].x)*(map[i].x-map[j].x)+(map[i].y-map[j].y)*(map[i].y-map[j].y));ans=min(ans,dism[i]+dism[j]+m);}for(int i=1;i<=n;i++) ans=max(ans,dism[i]);printf("%.6lf",ans);    return 0;
}