记录编号	154906	评测结果	AAAAAAAAAA
题目名称	[NOI 1997]最优乘车	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.222 s
提交时间	2015-03-25 18:30:05	内存使用	1.51 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cmath>
using namespace std;
int n,m;
char s[20000];
int a[555][555];
int main()
{
	freopen("bustravel.in","r",stdin);
	freopen("bustravel.out","w",stdout);
	cin>>m>>n;
	for (int i=1;i<=n;++i)
	 for (int j=1;j<=n;++j)
	  a[i][j]=10000000;
	getchar();
	for (int i=1;i<=m;++i)
	{
		gets(s);
		int z=0;
		int l=strlen(s),p=0,jl[550];
		for (int j=0;j<=l;++j)
		 if (s[j]>='0'&&s[j]<='9')
		  {
		  	z=z*10+(int)(s[j]-48);
		  }
		 else 
		 {
		 	p++;
		 	jl[p]=z;
		 	z=0;
		 }
		for (int j=1;j<=p-1;++j)
		 for (int k=j+1;k<=p;++k)
		   a[jl[j]][jl[k]]=0;
	}
	for (int k=1;k<=n;++k)
	 for (int i=1;i<=n;++i)
	 if (i!=k)
	  for (int j=1;j<=n;++j)
	   if (j!=i)
	   {
	   	if (a[i][k]+a[k][j]+1<a[i][j]) a[i][j]=a[i][k]+a[k][j]+1;
	   }
	if (a[1][n]!=10000000) cout<<a[1][n];
	 else cout<<"NO";
}