2178.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2178 on 2006-03-23 at 20:04:08 */ 
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
using namespace std;

const int MAX = 1024;
const int N_MAX = 64;
const int L = 16;
const double INF = 1e10;

struct cmp {
	bool operator ()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) < 0;
	}
};

class Point {
public:
	int x, y;
	double d;
	Point(int a = 0, int b = 0) : x(a), y(b), d(0) {}
	double dis(const Point&) const;
};
double Point::dis(const Point& p) const {
	return d+sqrt(1.0*(x-p.x)*(x-p.x)+(y-p.y)*(y-p.y));
}

class City {
public:
	char name[L];
	int link[N_MAX], ln, cn, deg;
	Point cs[N_MAX];
	void make();
	void add(int);
	void update(const City&);
};
void City::make() {
	ln = deg = 0;
	int n; scanf("%d", &n);
	for(cn = 0; cn < n; cn++) {
		int x, y; scanf("%d %d", &x, &y);
		cs[cn] = Point(x, y);
	}
}
void City::add(int m) {
	link[ln++] = m; deg++;
}
void City::update(const City& c) {
	int i, j;
	if(deg == 0) return;
	deg--;
	for(i = 0; i < cn; i++) {
		double md = INF;
		for(j = 0; j < c.cn; j++)
			md = min(md, c.cs[j].dis(cs[i]));
		cs[i].d += md;
	}
}

map<const char*, int, cmp> dict;

int main()
{
	City city[MAX];
	int i, n;

	while(scanf("%d", &n) != EOF && n != 0) {
		dict.clear();
		for(i = 0; i < n; i++) {
			scanf("%s", city[i].name); dict[city[i].name] = i;
			city[i].make();
		}
		for(i = 1; i < n; i++) {
			char cn1[L], cn2[L]; scanf("%s %s", cn1, cn2);
			int o1 = dict.find(cn1)->second, o2 = dict.find(cn2)->second;
			city[o1].add(o2); city[o2].add(o1);
		}
		int top = 0, stack[MAX];
		for(i = 0; i < n; i++)
			if(city[i].deg <= 1) stack[top++] = i;
		while(top > 1) {
			int p = stack[--top]; city[p].deg--;
			for(i = 0; i < city[p].ln; i++) {
				int o = city[p].link[i];
				city[o].update(city[p]);
				if(city[o].deg == 1) stack[top++] = o;
			}
		}
		int fin = stack[0]; double best = INF;
		for(i = 0; i < city[fin].cn; i++)
			best = min(best, city[fin].cs[i].d);
		printf("%.1lf\n", best);
	}
	
	return 0;
}