3058322_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>
#define inf 2100000000

using namespace std;

int f, m;
int map[101][101];
int dis[101];
int mark[101];
int A, B;

void solve()
{
	int i, j, v;
	int min;

	for(i = 0; i < f; i++)
	{
		dis[i] = inf;
		mark[i] = 0;
	}
	dis[A] = 0;
	for(i = 0; i < f; i++)
	{
		min = inf;
		for(j = 0; j < f; j++)
		{
			if(!mark[j]&&dis[j]<min)
			{
				min = dis[j];
				v = j;
			}
		}
		mark[v] = 1;
		for(j = 0; j < f; j++)
		{
			if(map[v][j]!=0&&dis[v]+map[v][j]<dis[j])
			{
				dis[j] = dis[v]+map[v][j];
			}
		}
	}
}

int main()
{
	int i, j, t, k;

	scanf("%d%d%d",&f,&A,&B);
	A--;B--;
	memset(map,-1,sizeof(map));
	for(i = 0; i < f; i++)
	{
		scanf("%d",&k);
		scanf("%d",&t);
		t--;
		map[i][t] = 0;
		for(j = 1; j < k; j++)
		{
			scanf("%d",&t);
			t--;
			map[i][t] = 1;
		}
	}
	solve();
	if(dis[B]==inf)
		dis[B] = -1;
	printf("%d\n",dis[B]);
	return 0;
}