pku1847.cpp

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

#include <stdio.h>
#define TheMax 10000
#define SZ 110
int Dis[SZ][SZ];

int N, A, B;

int DIJ()
{
	int minD[SZ];
	int st[SZ];
	int u, min, i, j;

	for (i = 1; i <= N; i++)
	{
		minD[i] = Dis[A][i];
		st[i] = 0;
	}
	st[A] = 1;
	
	for (j = 1; j < N; j++)
	{
		u = -1;
		min = TheMax;
		for (i = 1; i <= N; i++)
		{
			if (!st[i] && min > minD[i])
			{
				min = minD[i];
				u = i;
			}
		}
		if (u == -1)
		{
			break;
		}
		st[u] = 1;
		for (i = 1; i <= N; i++)
		{
			if (!st[i] && minD[i] > min + Dis[u][i])
			{
				minD[i] = min + Dis[u][i];
			}
		}
	}
	return minD[B];
}

int main()
{
	int i, k, p, j, ans;
	scanf("%d%d%d", &N, &A, &B);
	for (i = 1; i <= N; i++)
	{
		for (j = 1; j <= N; j++)
		{
			Dis[i][j] = TheMax;
		}
	}
	for (i = 1; i <= N; i++)
	{
		scanf("%d", &k);
		for (j = 0; j < k; j++)
		{
			scanf("%d", &p);
			Dis[i][p] = !!j;
		}
	}
	ans = DIJ();
	if (ans >= 1000)
	{
		ans = -1;
	}
	printf("%d\n", ans);
	return 0;
}