学步园

题目：tzc2731

方法：bfs

代码：

#include <iostream>
#include <queue>
using namespace std;

struct node
{
	int n,num;
};
int n,m;
bool g[1005][1005],visited[1005];
int s,e;

void bfs()
{
	queue <node> q;
	node pre,tmp;
	pre.n=s;pre.num=0;
	q.push(pre);
	while(!q.empty())
	{
		pre=q.front();
		q.pop();
		int i;
		if(pre.n==e)
		{
			cout<<pre.num-1<<endl;return;
		}
		for(i=1;i<=n;i++)
		{
			tmp.n=i;tmp.num=pre.num+1;
			if(visited[tmp.n]==0&&g[pre.n][tmp.n]==1)
			{
				if(tmp.n==e)
				{
					cout<<tmp.num-1<<endl;return;
				}
				q.push(tmp);visited[tmp.n]=1;
			}
		}
	}
	cout<<"No solution"<<endl; 
}

int main(int argc, char *argv[])
{
	while(cin>>n>>m&&(n||m))
	{
		int i;
		memset(g,0,sizeof(g));
		memset(visited,0,sizeof(visited));
		for(i=1;i<=m;i++)
		{
			int a,b;
			cin>>a>>b;
			g[a][b]=1;g[b][a]=1;
		}
		cin>>s>>e;
		bfs();
	}
	return 0;
}