2434.cpp

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

/* This Code is Submitted by wywcgs for Problem 2434 on 2007-01-03 at 13:26:25 */
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 1024;

bool g[N][N];
int n, m;

int dis(int, int);

int main()
{
	while(scanf("%d %d", &m, &n) != EOF && n != 0) {
		memset(g, false, sizeof(g));
		for(int i = 0; i < m; i++) {
			int p, pn[N]; scanf("%d", &p);
			for(int j = 0; j < p; j++) scanf("%d", &pn[j]);
			for(int j = 0; j < p; j++)
				for(int k = j+1; k < p; k++)
					g[pn[j]][pn[k]] = g[pn[k]][pn[j]] = true;
		}
		int d = dis(0, n-1);
		if(d == 1) printf("I do know wywcgs!\n");
		else if(d < 0) printf("I can never know wywcgs!\n");
		else printf("I can know wywcgs by at most %d person(s)!\n", d-1);
	}
	
	return 0;
}

int dis(int src, int dis)
{
	int d[N]; memset(d, -1, sizeof(d));
	queue<int> Q; Q.push(src); d[src] = 0;
	while(!Q.empty()) {
		int u = Q.front(); Q.pop();
		for(int i = 0; i < n; i++)
			if(d[i] == -1 && g[u][i])
				{ d[i] = d[u]+1; Q.push(i); }
		if(d[dis] != -1) break;
	}
	return d[dis];
}