【acwing】1125. 牛的旅行***(floyd)

穿越隧道

1.floyd求出任意两点之间的最短距离
2.求maxd[i],表示和i联通的且距离i最远的点的距离
3.
情况1：所有maxd[i]的最大值
情况2：枚举在哪两个点之间连边。i，j，需要满足d[i,j] = INF.maxd[i] + dis[i,j] + maxd[j];

#include <bits/stdc++.h>
#define x first
#define y second 
using namespace std;
typedef pair<double,double> pii;
const int N = 2e2 + 10;
const double INF = 1e20;
char g[N][N];
int n,m;
pii q[N];
double dis[N][N], maxd[N];
void floyd(){
    //floyd求出任意两点之间的最短距离
	for(int k = 0; k < n; k++){
    
		for(int i = 0; i < n; i++){
    
			for(int j = 0; j < n; j++){
    
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}
}
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){
    
				if(g[i][j] == '1'){
    //说明联通，求两个点的路径
					dis[i][j] = get_dist(q[i],q[j]);
				}
				else
					dis[i][j] = INF;
			}
		}
	}
	floyd();
	for(int i = 0; i < n; i++){
    
		for(int j = 0; j < n; j++){
    
			if(dis[i][j] < INF){
    //联通说明距离小于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));
	return 0;
}