1516.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1516 on 2005-10-07 at 10:55:50 */ 
#include <cstdio>
#include <cstring>
#define  MAX  256

int main()
{
	long fib[MAX][MAX];
	int n, a, b, r;
	int i, j, k;
	char com[32];
	
	while(scanf("%d", &n) == 1) {
		if(n == 0) {
			return 0;
		} else {
			memset(fib, 0, sizeof(fib));
			while(scanf("%d %d", &a, &b) == 2) {
				if(a == 0 && b == 0) {
					break;
				} else {
					scanf("%s", com);
					for(i = 0; com[i] != 0; i++) {
						fib[a][b] |= 1 << (com[i] - 'a');
					}
				}
			}
			for(i = 1; i <= n; i++) {
				fib[i][i] = 0xFFFFFFFF;
			}
			for(k = 1; k <= n; k++) {
				for(i = 1; i <= n; i++) {
					for(j = 1; j <= n; j++) {
						fib[i][j] |= fib[i][k] & fib[k][j];
					}
				}
			}
			while(scanf("%d %d", &a, &b) == 2) {
				if(a == 0 && b == 0) {
					break;
				} else {
					if(fib[a][b] != 0) {
						r = fib[a][b];
						for(i = 0; i < 26; i++) {
							if(r % 2 == 1) {
								putchar('a'+i);
							}
							r /= 2;
						}
					} else {
						putchar('-');
					}
					putchar('\n');
				}
			}
			putchar('\n');
		}
	}
	
	return 0;
}