[USACO2.4]牛的旅行 Cow Tours

这我真的不知道是哪里错了……

也许是我没读透题？？

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 1000000005
#define qwq printf("qwq\n");

using namespace std;

int read() {
    register int x = 0,f = 1;register char ch;
    ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
    while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
}

struct node {
	int x, y;
}area[155];

int n, t1, t2, flag, fa[155], q1[155], q2[155];

double ans, maxx, map[155][155];

char s[155];

double make_distant(int a, int b) {
	double x1 = area[a].x, y1 = area[a].y, x2 = area[b].x, y2 = area[b].y;
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}



int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}

int main() {
//	freopen("P1522.out", "w", stdout);
	n = read();
	for(int i = 1; i <= n; i++) {
		area[i].x = read();
		area[i].y = read();
		fa[i] = i;
	}
	for(int i = 1; i <= n; i++) {
		cin >> s;
		for(int j = 0; j < n; j++) {
			if(s[j] - '0' == 1) map[i][j + 1] = make_distant(i, j + 1), fa[find(i)] = find(j + 1);
			else map[i][j + 1] = INF;
		}
	}
	for(int k = 1; k <= n; k++)
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++) {
				if(i == j || j == k || i == k) continue;
				map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
			}
	for(int i = 1; i <= n; i++) {
		if(find(i) == find(1)) q1[++t1] = i;
		else q2[++t2] = i;
	}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++) {
			if(map[i][j] == INF) continue;
			maxx = max(maxx, map[i][j]);
		}
	ans = INF;
	for(int i = 1; i <= t1; i++)
		for(int j = 1; j <= t2; j++) {
			double dist1 = 0, dist2 = 0;
			for(int k = 1; k <= t1; k++) {
				if(i == k) continue;
				dist1 = max(dist1, map[q1[i]][q1[k]]);
			}
			for(int k = 1; k <= t2; k++) {
				if(j == k) continue;
				dist2 = max(dist2, map[q2[j]][q2[k]]);
			}
			ans = min(ans, max(maxx, dist1 + dist2 + make_distant(q1[i], q2[j])));
//	printf("(%d , %d) < -- > (%d , %d), ans = %llf\n", area[q1[i]].x, area[q1[i]].y, area[q2[j]].x, area[q2[j]].y, ans);
		}
//	for(int i = 1; i <= n; i++) {
//		for(int j = 1; j <= n; j++) printf("%.3llf ", map[i][j] == INF ? 0 : map[i][j]); cout << endl;
//	}
//	cout << make_distant(2, 5) << endl;
//	cout << map[1][5] << endl;
	printf("%.6lf\n", ans);
    return 0;
}