跳至正文

1 条题解

  • 0
    @ 2026-10-2 2:21:54

    计算每点最远距离及原全局直径,再枚举跨分量边最小化新全局直径。

    #include <bits/stdc++.h>
    using namespace std;
    
    int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
    
    int n;cin>>n;vector<pair<int,int>>a(n);for(auto&[x,y]:a)cin>>x>>y;const long double INF=numeric_limits<long double>::infinity();vector<vector<long double>>d(n,vector<long double>(n,INF));auto distance=[&](int i,int j){return hypotl((long double)a[i].first-a[j].first,(long double)a[i].second-a[j].second);};for(int i=0;i<n;i++){string s;cin>>s;for(int j=0;j<n;j++)if(i==j)d[i][j]=0;else if(s[j]=='1')d[i][j]=distance(i,j);}for(int k=0;k<n;k++)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]);vector<long double>ecc(n);long double original=0;for(int i=0;i<n;i++){for(int j=0;j<n;j++)if(isfinite(d[i][j]))ecc[i]=max(ecc[i],d[i][j]);original=max(original,ecc[i]);}long double answer=INF;for(int i=0;i<n;i++)for(int j=0;j<i;j++)if(!isfinite(d[i][j]))answer=min(answer,max(original,ecc[i]+distance(i,j)+ecc[j]));if(!isfinite(answer))answer=original;cout<<fixed<<setprecision(6)<<answer<<"\n";
    
    return 0;
    }
    
    • 1

    信息

    ID
    4018
    时间
    1000ms
    内存
    128MiB
    难度
    5
    标签
    递交数
    0
    已通过
    0
    上传者