1121.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1121 on 2005-12-11 at 16:30:38 */ 
#include <cstdio>
#include <cstring>
#include <list>
#include <queue>
using namespace std;

const int MAX = 10240;
const int HASH_LIMIT = 9973;
const int L_MAX = 48;
const int L_LIMIT = 256;
const char master[] = "Erdos, P.";

class HashTable {
public:
	static int hash(const char*);
	list<int> table[HASH_LIMIT];
	void init();
};
int HashTable::hash(const char* str) {
	int i, l = (strlen(str)+1) / 2;
	unsigned int ret = 0;
	unsigned short *s = (unsigned short*)str;
	for (i = 0; i < l; i++) {
		ret ^= (s[i] << (i & 0x0F));
	}
	return ret % HASH_LIMIT;
}
void HashTable::init() {
	int i;
	for(i = 0; i < HASH_LIMIT; i++) {
		table[i].clear();
	}
}

const int master_code = HashTable::hash(master);

class Author {
public:
	char name[L_MAX];
	int erdos;
	list<int> publish;
	void clear();
};
void Author::clear() {
	publish.clear();
	erdos = MAX;
}

HashTable ht;
Author author[MAX];

int find(const char*, const int);

int main()
{
	int p, n, an;
	int t, i, j, k;
	char line[L_LIMIT];

	for(t = 1; scanf("%d %d", &p, &n) != EOF && n*p != 0; t++) {
		an = 0;
		ht.init();
		for(i = 0; i < p; i++) {
			int stack[L_MAX], top = 0;
			do {
				scanf("%s", line);
				scanf("%[^,:]", line+strlen(line));
				int code = HashTable::hash(line);
				int o = find(line, code);
				if(o == -1) {
					author[an].clear();
					strcpy(author[an].name, line);
					ht.table[code].push_back(an);
					o = an++;
				}
				stack[top++] = o;
			} while(getchar() != ':');
			gets(line);
			for(j = 0; j < top; j++) {
				for(k = 0; k < top; k++) {
					if(j != k) {
						author[stack[j]].publish.push_back(stack[k]);
					}
				}
			}
		}
		queue<int> queue;
		int begin = find(master, master_code);
		if(begin != -1) {
			author[begin].erdos = 0;
			queue.push(begin);
			while(!queue.empty()) {
				int t = queue.front();
				queue.pop();
				list<int>::iterator it;
				list<int> *per = &author[t].publish;
				if(!per->empty()) {
					for(it = per->begin(); it != per->end(); it++) {
						if(author[*it].erdos > author[t].erdos + 1) {
							author[*it].erdos = author[t].erdos + 1;
							queue.push(*it);
						}
					}
				}
			}
		}
		printf("Database #%d\n", t);
		for(i = 0; i < n; i++) {
			gets(line);
			int code = HashTable::hash(line);
			int o = find(line, code);
			printf("%s: ", line);
			if(o == -1 || author[o].erdos == MAX) {
				printf("infinity\n");
			} else {
				printf("%d\n", author[o].erdos);
			}
		}
		putchar('\n');
	}
	
	return 0;
}

int find(const char* s, const int code)
{
	if(!ht.table[code].empty()) {
		list<int>::iterator it;
		for(it = ht.table[code].begin(); it != ht.table[code].end(); it++) {
			if(!strcmp(s, author[*it].name)) {
				return *it;
			}
		}
	}
	return -1;
}