2781.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 83 行

//#define debug 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define INF 3000000
#define NMAX 1000000
int N;
typedef struct 
{
	int len;
	int next[101];
}DATA;
DATA a[NMAX];
int st,ed;
void input()
{
	int i,j;
	scanf("%d",&N);
	int tmp;
	for(i=0;i<N;i++)
	{
		scanf("%d%d",&tmp,&a[i].len);
		for(j=0;j<a[i].len;j++)
		{
			scanf("%d",&a[i].next[j]);
		}
		a[i].next[j]=-1;
	}
	scanf("%d%d",&st,&ed);
}
int m[NMAX]={0};
int p,q;
int que[NMAX];

void solve()
{
	int i;
	for(i=0;i<N;i++)
		m[i]=INF;
	que[0]=st;
	p=0;
	q=1;
	m[st]=0;
	int cp;
	while(p<q)
	{
		cp=que[p++];
		for(i=0;i<a[cp].len;i++)
		{
			if(m[a[cp].next[i]]>m[cp]+1)
			{
				m[a[cp].next[i]]=m[cp]+1;
				que[q++]=a[cp].next[i];
			}
		}

	}
	printf("%d %d %d",st,ed,m[ed]-1);
	
}
int main()
{

#if _DEBUG	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);

#endif
	input();
	solve();
	
		
#if _DEBUG
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}