> #include <iostream>
> using namespace std;
> 
> int status[100000][101];
> int flag[200000];
> int deque[200000];
> 
> int main()
> {
> 
> 	int caseNum;
> 	int eachCaseNum;
> 	int i, j, p, q;
> 	int beg, end, tmpBeg;
> 	int ans;
> 	bool dFlag;
> 
> 	while (scanf("%d", &caseNum) != EOF)
> 	{		
> 		for (i=0; i<caseNum; i++)
> 		{
> 			scanf("%d", &eachCaseNum);
> 			scanf("%d", &eachCaseNum);
> 			status[i][0] = eachCaseNum;
> 			for (j=1; j<=eachCaseNum; j++)
> 			{
> 				scanf("%d", &status[i][j]);
> 			}
> 		}
> 		
> 		scanf("%d", &beg);
> 		scanf("%d", &end);
> 		tmpBeg = beg;
> 
> 		memset(flag, 0, 200000);
> 		memset(deque, 0, 200000);
> 
> 		p = 0;
> 		q = 0;
> 
> 		flag[beg] = -1;
> 		ans = 0;
> 		dFlag = false;
> 
> 		while (1)
> 		{
> 			for (i=1; i<=status[beg][0]; i++)
> 			{
> 				if (flag[status[beg][i]] != -1)
> 				{
> 					flag[status[beg][i]] = -1;
> 					deque[q++] = status[beg][i];
> 				}
> 			}
> 
> 			if (!dFlag)
> 			{
> 				deque[q++] = -1;
> 				dFlag = true;
> 			}
> 
> 			while (deque[p] == -1)
> 			{
> 				p++;
> 				ans++;
> 				dFlag = false;
> 			}
> 
> 			beg = deque[p++];
> 
> 			if (beg == end)
> 			{
> 				printf("%d %d %d\n", tmpBeg, end, ans);
> 				break;
> 			}
> 		}
> 		
> 	}
> 	return 0;
> }

• semonteer 我就是用BFS的... (0) qywyh_scut 2006-03-27 22:57:08