FLOYD算法模板练习题，+FLOODFILL，没什么可说

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cstring>
using namespace std;

const int MAXN = 165;
const double INF = 1e20;
int n, m, id = 0, field[MAXN], vis[MAXN];
double tot_ans, dis[MAXN][MAXN], md[MAXN], maxdis[MAXN];
struct node{
	double x, y;
}a[MAXN];

double calc(node x, node y){
	double disx = abs(x.x - y.x);
	double disy = abs(x.y - y.y);
	return sqrt(disx*disx + disy*disy);
}

void dfs(int u, int answer){
	vis[u] = 1; field[u] = answer;
	for (int i = 1; i <= n; i++)
		if (!vis[i] && dis[i][u] != INF)
			dfs(i, answer);
}

int main(){
	freopen("cowtour.in", "r", stdin);
	freopen("cowtour.out", "w", stdout);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i].x >> a[i].y;
	memset(dis, 0x3f, sizeof(dis));
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++){
			char c; cin >> c;
			if (c == '1' || i == j)
				dis[i][j] = calc(a[i], a[j]);
			else dis[i][j] = INF;
		}
	
	for (int i = 1; i <= n; i++)
		if (!vis[i]) dfs(i, ++id);
	
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (dis[i][j] > dis[i][k] + dis[k][j])
					dis[i][j] = dis[i][k] + dis[k][j];
	
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++)
			if (dis[i][j] < INF)
				md[i] = max(md[i], dis[i][j]);
		maxdis[field[i]] = max(maxdis[field[i]], md[i]);
	}
	
	tot_ans = INF;
	for (int i = 1; i <= n; i++)
		for (int j = i+1; j <= n; j++)
			if(field[i] != field[j]){
				double maxd = max(max(maxdis[field[i]],maxdis[field[j]]),md[i]+md[j]+calc(a[i],a[j]));
				tot_ans = min(tot_ans, maxd);
			}
	
	printf("%.6f\n", tot_ans);
	
	return 0;
}