1565.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1565 on 2005-10-23 at 10:10:46 */ 
#include <cstdio>

const int MAX = 64;

int main()
{
	int d[MAX][MAX];
	long long past[MAX][MAX], r, reach;
	int list[MAX], top;
	int n, m;
	int i, j, k, p;
	
	while(scanf("%d", &n) == 1) {
		for(i = 0; i <= n; i++) {
			for(j = 0; j <= n; j++) {
				d[i][j] = MAX;
				past[i][j] = 0;
			}
		}
		for(i = 1; i <= n; i++) {
			d[i][i] = 0;
			while(true) {
				scanf("%d", &p);
				d[i][p] = 1;
				if(getchar() == '\n') {
					break;
				}
			}
		}
		for(i = 1; i <= n; i++) {
			for(j = i; j <= n; j++) {
				if(d[i][j] != MAX) {
					past[i][j] = past[j][i] = ((long long)1 << i) | ((long long)1 << j);
				}
			}
		}
		for(k = 1; k <= n; k++) {
			for(i = 1; i <= n; i++) {
				for(j = 1; j <= n; j++) {
					if(d[i][j] > d[i][k]+d[k][j]) {
						d[i][j] = d[i][k]+d[k][j];
						past[i][j] = past[i][k] | past[k][j];
					} else if(d[i][j] == d[i][k]+d[k][j] && d[i][j] != MAX) {
						past[i][j] |= past[i][k] | past[k][j];
					}
				}
			}
		}
		scanf("%d", &m);
		reach = ((long long)1 << (n+1)) - 2;
		for(k = 0; k < m; k++) {
			top = r = 0;
			while(true) {
				scanf("%d", &list[top++]);
				if(getchar() == '\n') {
					break;
				}
			}
			for(i = 0; i < top && r != reach; i++) {
				for(j = i+1; j < top && r != reach; j++) {
					r |= past[list[i]][list[j]];
				}
			}
			if(r == reach) {
				printf("yes\n");
			} else {
				printf("no\n");
			}
		}
	}
	
	return 0;
}