pku2781.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 70 行

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct 
{
	int x;
	int nxt;
}Node;

Node nd[10100000];
int st[100001];
int qu[100001];
int N;

void input(int S)
{
	int i, j, nc, e, id, now;
	e = 100001;
	memset(st, -1, sizeof(st));
	for (i = 0; i < S; i++)
	{
		scanf("%d%d", &id, &nc);
		nd[id].nxt = -1;
		now = id;
		for (j = 0; j < nc; j++)
		{
			scanf("%d", &nd[e].x);
			nd[e].nxt = -1;
			nd[now].nxt = e;
			now = e;
			e++;
		}
	}
}

int main()
{
	int i, j, h, e, p, uf, c1, c2;
	scanf("%d", &N);
	input(N);
	scanf("%d %d", &c1, &c2);
	h = 0;
	e = 1;
	qu[0] = c1;
	st[c1] = 0;
	uf = 1;
	while (h < e && uf)
	{
		p = nd[qu[h]].nxt;
		while (p != -1)
		{
			if (nd[p].x == c2)
			{
				uf = 0;
				printf("%d %d %d\n", c1, c2, st[qu[h]]);
				break;
			}
			if (st[nd[p].x] == -1)
			{
				st[nd[p].x] = st[qu[h]] + 1;
				qu[e] = nd[p].x;
				e++;
			}
			p = nd[p].nxt;
		}
		h++;
	}
	return 0;
}