AcWing 1125 牛的旅行

解题思路：

1、求出任意两点之间的最短距离

2、求maxd[i]，表示和i连通的且距离i最远的点的距离

3、 情况1：所有maxd[i]的最大值
情况2：枚举在哪两个点之间连边。i，j需要满足dis[i,j]=INF。maxd[i] + dist[i,j] + maxd[j]

# include <bits/stdc++.h>
using namespace std;

# define x first
# define y second
const int maxn = 150 + 5;
const double inf = 1e20;
typedef pair<int , int> pII;
int n;
pII q[maxn];
char g[maxn][maxn];
double dis[maxn][maxn] , maxd[maxn];
inline double get_dist(pII a , pII b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}
int main() {
    cin >> n;
    for (int i = 0 ; i < n ; i ++) {
        cin >> q[i].x >> q[i].y;
    }
    for (int i = 0 ; i < n ; i ++) {
        cin >> g[i];
    }
    for (int i = 0 ; i < n ; i ++) {
        for (int j = 0 ; j < n ; j ++) {
            if (i != j) {//如果这两个点之间有边算距离不然就是inf 
                if (g[i][j] == '1') dis[i][j] = get_dist(q[i] , q[j]);
                else dis[i][j] = inf;
            }
        }
    }
    for (int k = 0 ; k < n ; k ++) {
        for (int i = 0 ; i < n ; i ++) {
            for (int j = 0 ; j < n ; j ++) {//Floyd求最短路 
                dis[i][j] = min(dis[i][j] , dis[i][k] + dis[k][j]);
            }
        }
    }
    for (int i = 0 ; i < n ; i ++) {
        for (int j = 0 ; j < n ; j ++) {
            if (dis[i][j] < inf) {//如果这两个点之间可以互相到达 
                maxd[i] = max(maxd[i] , dis[i][j]);//如思路 
            } 
        }
    }
    double res1 = 0;
    for (int i = 0 ; i < n ; i ++) {
        res1 = max(res1 , maxd[i]);
    }
    double res2 = inf;
    for (int i = 0 ; i < n ; i ++) {
        for (int j = 0 ; j < n ; j ++) {
            if (dis[i][j] >= inf) {//枚举需要连接的两个点 如果没有连通，就连上 
                res2 = min(res2 , get_dist(q[i] , q[j]) + maxd[i] + maxd[j]);
            }
        }
    }
    printf("%.6lf\n" , max(res1 , res2));
}