pku2457.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#define size 1001

typedef struct Node
{
	int x;
	int fa;
}Node;

Node q[size];
bool pt[size][size];
int N, K;
int s, e;
bool vis[size];
int path[size];

void BFS()
{
	int hd, tl, i, found = 0;
	
	hd = 0;
	tl = 1;
	q[hd].x = 1;
	vis[1] = 1;
	while (hd < tl)
	{
		if (found)
		{
			break;
		}
		for (i = 0; i < size; i++)
		{
			if (!vis[i] && pt[q[hd].x][i])
			{
				q[tl].x = i;
				vis[i] = 1;
				q[tl].fa = hd;
				if (i == K)
				{
					found = 1;
					break;
				}
				tl++;
			}
		}
		hd++;
	}
	if (found == 0)
	{
		printf("-1\n");
	}
	else
	{
		i = 0;
		path[i++] = q[tl].x;
		while (tl != 0)
		{
			tl = q[tl].fa;
			path[i++] = q[tl].x;
		}
		printf("%d\n", i);
		i--;
		while (i >= 0)
		{
			printf("%d\n", path[i]);
			i--;
		}
	}
}

int main()
{
	scanf("%d %d", &N, &K);
	memset(pt, 0, sizeof(pt));
	memset(vis, 0, sizeof(vis));
	while (N--)
	{
		scanf("%d %d", &s, &e);
		pt[s][e] = 1;
	}
	BFS();
	return 0;
}