题目

记录

WA on 7 8 9

/*
Luogu P1522 牛的旅行 Cow Tours
https://www.luogu.com.cn/problem/P1522
*/
#include "iostream"
#include "queue"
#include "cmath"
using namespace std;
int n, head[155], idx, groups;
double g[155][155], d, farms[155], farthest[155]; // 一片牧区的最长距离、一个点的最远距离
struct edge{
    int to, nxt;
    double w;
}e[150*150+5];
struct point{
    int x, y, belong;
    point(){
        this->belong=-1;
    }
}p[155];
double euclidean(int i, int j){
    return sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));
}
void add_edge(int u, int v, double w){
    e[++idx].to=v;
    e[idx].w=w;
    e[idx].nxt=head[u];
    head[u]=idx;
}
void bfs(int start){
    groups++;
    p[start].belong=groups;
    queue<int>q;
    q.push(start);
    while(!q.empty()){
        int temp=q.front(), to;
        q.pop();
        for(int i=head[temp];i;i=e[i].nxt){
            to=e[i].to;
            if(p[to].belong==-1){
                p[to].belong=groups;
                q.push(to);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> p[i].x >> p[i].y;
    }
    char c;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin >> c;
            if(c=='1'){
                d=euclidean(i, j);
                add_edge(i, j, d);
                g[i][j]=d;
                if(farthest[i]<d) farthest[i]=d;
            }else if(i==j) g[i][j]=0;
            else g[i][j]=0x3f3f3f3f;
        }
    }
    for(int i=1;i<=n;i++){
        if(p[i].belong==-1){
            bfs(i);
        }
    }
    double ans=0x3f3f3f3f;
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                d=g[i][k]+g[k][j];
                if (d < g[i][j]) {
                    g[i][j] = d;
                    if (farthest[i] < d) farthest[i] = d;
                    if (farthest[j] < d) farthest[j] = d;
                    if (farms[p[i].belong] < d) farms[p[i].belong] = d;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(p[i].belong==p[j].belong) continue;
            d=farthest[i]+farthest[j]+euclidean(i, j);
            if(farms[p[i].belong]>d) d=farms[p[i].belong];
            if(farms[p[j].belong]>d) d=farms[p[j].belong];
            if(d<ans){
                ans=d;
            }
        }
    }
    printf("%.6f", ans);
}