记录编号	34010	评测结果	AAAAAAAAAA
题目名称	[NOI 1997]最优乘车	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.325 s
提交时间	2011-11-25 22:25:39	内存使用	1.42 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAXN=10000000;
int Bus[101][501];
int Map[501][501];
int N,M;

void init()
{
	string line;
	scanf("%d %d\n",&M,&N);
	
	for (int i=1;i<=N;i++)
		for (int j=1;j<=N;j++)
			Map[i][j]=MAXN;
	
	for (int i=1;i<=M;i++)
	{
		Bus[i][0]=0;
		getline(cin,line);
		int tmp=0;
		int len=line.length();
		int top=0;
		while(top<len)
		{
			if(isdigit(line[top]))
			{
				tmp=tmp*10+line[top]-'0';
				top++;
				continue;
			}
			if(line[top]==' ')
			{
				Bus[i][0]++;
				Bus[i][Bus[i][0]]=tmp;
				tmp=0;
				top++;
				continue;
			}
		}
		if(tmp>0)
		{
			Bus[i][0]++;
			Bus[i][Bus[i][0]]=tmp;
		}
	}
	
	int t1,t2;
	for (int i=1;i<=M;i++)
	{
		for (int j=1;j<=Bus[i][0];j++)
		{
			for (int k=j;k<=Bus[i][0];k++)
			{
				t1=Bus[i][j];
				t2=Bus[i][k];
				Map[t1][t2]=0;
			}
		}
	}
}

void Floyd()
{
	int tmp;
	for (int k=1;k<=N;k++)
	{
		for (int i=1;i<=N;i++)
		{
			for (int j=1;j<=N;j++)
			{
				tmp=Map[i][k]+Map[k][j]+1;
				if(tmp<Map[i][j])
					Map[i][j]=tmp;
			}
		}
	}
	if(Map[1][N]==MAXN)
		printf("NO\n");
	else
		printf("%d\n",Map[1][N]);
}

int main()
{
	freopen("bustravel.in","r",stdin);
	freopen("bustravel.out","w",stdout);
	init();
	Floyd();
	return 0;
}