AcWing 1125. 牛的旅行 题解（最短路、直径）

AcWing 1125. 牛的旅行
比较麻烦的是求直径和连接两个不同牧场的点之后求直径的运算，floyd求最短路在这里体现的必要性不是很强

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define db double

typedef pair<db, db>PDD;

const int N = 200;
const double MNF = 1e20;

int n, m;
char g[N][N];  //储存矩阵 
PDD q[N];  //储存坐标 
db d[N][N];  //储存最短距离
db maxd[N];  //储存同一片牧场内的最远距离

db get_dist(PDD a, PDD b){
      //求两个点之间的距离 
	db dx = a.x - b.x, 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) d[i][j] = 0;
			else if(g[i][j] == '1') d[i][j] = get_dist(q[i], q[j]);
			else d[i][j] = MNF;
		}
	}
	
	//Floyd求最短路 
	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]);
			}
		}
	}
	
	db res1 = 0;
	for(int i = 0; i < n ; i ++ ){
    
		for(int j = 0; j < n; j ++ ){
    
			if(d[i][j] < MNF / 2){
    
				//这里在我在疑惑为什么不能用矩阵中的1判断两个不联通的点
				//原因是同一个牧场内两个间接连通的点的矩阵的数也是1，所以不能用矩阵的值判断两个点是否是一个牧场
				maxd[i] = max(d[i][j], maxd[i]);  //求每个点的直径
			} 
		} 
		res1 = max(maxd[i], res1);
	}
	
	db res = MNF;  //初始化
	for(int i = 0; i < n; i ++ ){
    
		for(int j = 0; j < n; j ++ ){
    
			if(d[i][j] > MNF / 2){
      //这里在想为什么不能用矩阵中的0判断两个不联通的点
			//原因是同一个牧场内两个没有直接连通的点的矩阵数也是0，所以不能用矩阵判断两个点是否是一个牧场 
				res = min(res, maxd[i] + maxd[j] + get_dist(q[i], q[j]));
			}
		}
	} 
	
	printf("%.6lf\n", max(res, res1));
	return 0;
}