1690.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1690 on 2006-09-01 at 16:42:12 */ 
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
const int N = 128;
const int L = 64;
const char TED[] = "Ted";
const int TED_AGE = 100;

class Person {
public:
	char name[L];
	int age;
	void make(char* n) { strcpy(name, n); }
	void set(int a) { age = a; }
	void show() const { if(strcmp(name, TED)) printf("%s %d\n", name, TED_AGE-age); }
	bool operator <(const Person&) const;
};
bool Person::operator <(const Person& p) const {
	if(age != p.age) return age < p.age;
	else return strcmp(name, p.name) < 0;
}

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

map<const char*, int, cmp> dict;
Person p[N];
vector<pii> g[N];
int n;

int find(char*);
void birth(int, int);

int main()
{
	int T;
	
	scanf("%d", &T);
	for(int t = 1; t <= T; t++) {
		dict.clear(); n = 0;
		int m; scanf("%d", &m);
		for(int i = 0; i < m; i++) {
			char n1[L], n2[L]; int d;
			scanf("%s %s %d", n1, n2, &d);
			int o1 = find(n1), o2 = find(n2);
			g[o1].push_back(pii(o2, d));
		}
		int to = dict.find(TED)->second;
		birth(to, 0);
		sort(p, p+n);
		printf("DATASET %d\n", t);
		for(int i = 0; i < n; i++) p[i].show();
	}
	
	return 0;
}

int find(char* nm)
{
	if(!dict.count(nm)) { p[n].make(nm); dict[p[n].name] = n; g[n].clear(); n++;  }
	return dict.find(nm)->second;
}
void birth(int pn, int pg)
{
	p[pn].set(pg);
	for(int i = 0; i < g[pn].size(); i++)
		birth(g[pn][i].first, pg+g[pn][i].second);
}