USACO 2.4.3 – Cow Tours

#include <cstdio>
#include <cmath>
#define sq(a) ((a)*(a))

int main() {
	freopen("cowtour.in", "r", stdin), freopen("cowtour.out", "w", stdout);
	int p[151][2], n;
	double best_l = 0, d[151][151], best_s = 1e12;
	scanf("%d\n", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d\n", p[i], p[i] + 1);
		for (int j = 0; j < i; j++)
			d[i][j] =d[j][i] = sqrt(sq(p[i][0]-p[j][0]) + sq(p[i][1]-p[j][1]));
	}
	for (int i = 0; i < n; i++, getchar())
		for (int j = 0; j < n; j++)
			d[i][j] *= getchar() == '0' ? -1 : 1;

	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; best_l = k==n-1 ? max(best_l, d[i][j]):best_l, j++)
				if (d[i][k]>0 && d[k][j]>0)
					d[i][j] = d[i][j]<0? d[i][k]+d[k][j] : min(d[i][j], d[i][k]+d[k][j]);

	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			if (d[i][j] < 0) {
				double d1 = 0, d2 = 0;
				for (int k = 0; k < n; k++)
					d1 = max(d1, d[i][k]), d2 = max(d2, d[j][k]);
				best_s = min(best_s, d1 + d2 + -d[i][j]);
			}

	printf("%.6lf\n", max(best_s, best_l));
	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: