2159.cpp

来自「这是哈尔滨工业大学acmOJ的源代码」· C++ 代码 · 共 61 行

/*  This Code is Submitted by wywcgs for Problem 2159 on 2006-03-08 at 16:53:35 */ 
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 102400;

class People {
public:
	vector<int> know;
	void make();
};
void People::make() {
	know.clear();
	int i, kn; scanf("%d", &kn);
	for(i = 0; i < kn; i++) {
		int a; scanf("%d", &a);
		know.push_back(a);
	}
}

People peo[MAX];


int find(int, int);

int main()
{
	int n, i;
	
	while(scanf("%d", &n) != EOF) {
		for(i = 0; i < n; i++) {
			int o; scanf("%d", &o);
			peo[o].make();
		}
		int a, b; scanf("%d %d", &a, &b);
		printf("%d %d %d\n", a, b, find(a, b));
	}
	
	return 0;
}

int find(int src, int dis)
{
	int step[MAX];
	memset(step, -1, sizeof(step));
	queue<int> Q;
	while(!Q.empty()) Q.pop();
	Q.push(src); step[src] = 0;
	while(!Q.empty() && step[dis] == -1) {
		int i, p = Q.front(); Q.pop();
		for(i = 0; i < (int)peo[p].know.size(); i++) {
			int o = peo[p].know[i];
			if(step[o] == -1) { step[o] = step[p]+1; Q.push(o); }
		}
	}
	return step[dis]-1;
}