Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

一次AC 广搜 便可

Posted by zihuacs at 2010-08-03 09:48:19 on Problem 2781
#include <iostream>
#include <queue>
using namespace std;
int map[100000][101];
bool isUse[100000];
int qu[100001];
int n;
int s,e;
int qs,qt,qly;
int ans;
void BFS(void)
{
	int i;
	qu[0]=s;
	qs=0; qt=1; qly=qt-1;
	ans=0;
	while(qs<qt)
	{
		if(qs>qly)
		{
			ans++;
			qly=qt-1;
		}
		for(i=1; i<map[qu[qs]][0]+1; i++)
		{
			if(isUse[map[qu[qs]][i]]==false)
			{
				if(map[qu[qs]][i]==e)
				{
					return;
				}
				isUse[map[qu[qs]][i]]=true;
				qu[qt]=map[qu[qs]][i];
				qt++;
			}
		}
		qs++;
	}
}
int main(void)
{
	int i,j;
	int c;
	scanf("%d",&n);
	for(i=0; i<n; i++)
	{
		isUse[i]=false;
		scanf("%d",&c);
		scanf("%d",&map[c][0]);
		for(j=1; j<map[c][0]+1; j++)
		{
			scanf("%d",&map[c][j]);
		}
	}
	cin>>s>>e;
	BFS();
	cout<<s<<" "<<e<<" "<<ans<<endl;
	system("pause");
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator