原题链接
又是 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; }