3286375_ac_7063ms_8172k.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 68 行

#include <stdio.h>
#include <queue>
#include <algorithm>

using namespace std;

int n;
struct node
{
	int step;
	int id;
};

char visited[100000];
queue <node> que;
vector <int> net[100000];
int st, ed;

void bfs()
{
	node t, q;

	t.id = st;
	t.step = 0;
	que.push(t);
	visited[st] = '1';
	while(!que.empty())
	{
		t = que.front();
		que.pop();
		for(int i = 0; i < net[t.id].size(); i++)
		{
			if(visited[net[t.id][i]]!='1')
			{
				q.step = t.step + 1;
				q.id = net[t.id][i];
				visited[net[t.id][i]] = '1';
				que.push(q);
				if(q.id==ed)
				{
					printf("%d\n",q.step-1);
					return ;
				}
			}
		}
	}
}

int main()
{
	int i, j, t;
	int id, num;

	scanf("%d",&n);
	for(i = 0; i < n; i++)
	{
		scanf("%d%d",&id,&num);
		for(j = 0; j < num; j++)
		{
			scanf("%d",&t);
			net[id].push_back(t);
		}
	}
	scanf("%d%d",&st,&ed);
	printf("%d %d ",st,ed);
	bfs();
	return 0;
}