Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
150800 | 吴宗桦 | 牛的旅行 | C++ | 通过 | 100 | 5 MS | 452 KB | 1471 | 2024-06-08 14:46:45 |
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> using namespace std; const double INF = 1e10; int n,m; int cot[152][2]; double Dis[152][152]; double f[152]; double _(int i,int j){ return sqrt( (cot[i][0] - cot[j][0])* (cot[i][0] - cot[j][0])+ (cot[i][1] - cot[j][1])* (cot[i][1] - cot[j][1]) ); } int main(void){ cin>>n; for(int i=0;i<n;i++) cin>>cot[i][0]>>cot[i][1]; char c; for(int i=0;i<n;i++) for(int j=0;j<n;j++){ cin>>c; if(c=='1') Dis[i][j] = _(i,j); else if(i!=j) Dis[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++){ if(Dis[i][k]+Dis[k][j] < Dis[i][j]) Dis[i][j] = Dis[i][k]+Dis[k][j]; } double inner_max = 0; for(int i=0;i<n;i++) // 牧场最大直径 for(int j=0;j<n;j++){ if(Dis[i][j]!=INF){ f[i]=max(f[i],Dis[i][j]); inner_max = max(inner_max,f[i]); } } double outer_min = INF; for(int i=0;i<n;i++) // 连接后最小直径 for(int j=0;j<n;j++){ if(Dis[i][j]==INF){ outer_min = min(outer_min, f[i]+f[j]+_(i,j)); } } printf("%.6f\n",max(inner_max,outer_min)); return 0; }