记录编号	31627	评测结果	AAAAAAAAAAAAAA
题目名称	[USACO Feb08] 流星雨	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.082 s
提交时间	2011-11-03 11:43:58	内存使用	115.17 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int number,q[310][310],a[10000000][3],ji=0,qi=0,mo=0,answer=-1;
int f[5][2]={{1,0},{0,1},{-1,0},{0,-1},{0,0}};
void bfs(int x);
bool used[310][310]={{0}};
int main()
{
	freopen ("meteor.in","r",stdin);
	freopen ("meteor.out","w",stdout);
	scanf("%d",&number);
	for (int i=0;i<=301;i++)
	{
		for (int j=0;j<=301;j++)
		{
			used[i][j]=0;
			q[i][j]=100000;
		}
	}
	for (int i=0;i<number;i++)
	{
		int a,b,c;	
		scanf("%d%d%d",&a,&b,&c);
		for (int j=0;j<5;j++)
		{
			int e,r;
			e=a+f[j][0];
			r=b+f[j][1];
			if (e>=0&&r>=0&&e<=301&&r<=301)
			{
				used[e][r]=1;
				if (q[e][r]!=0)
				{
					if (q[e][r]>c)
					{
						q[e][r]=c;
					}
				}
				else
				{
					q[e][r]=c;
				}
			}
		}
	}
	if (used[0][0]==0)
	{
		cout<<0;
		return 0;
	}
	if (ji>=9000000)
	{
		cout<<-1;
		return 0;
	}
	used[0][0]=1;
	a[0][0]=0;
	a[0][1]=0;
	a[0][2]=0;
	while (qi<=mo)
	{
		bfs(qi);
		qi++;
	}
	if (answer==-1)
	{
		cout<<-1;
	}
	return 0;
}
void bfs(int x)
{
	if (used[a[x][0]][a[x][1]]==0)
	{
		cout<<a[x][2];
		answer=1;
		exit(0);
	}
	else
	{
		for (int i=0;i<5;i++)
		{
			int e,r;
			e=a[x][0]+f[i][0];
			r=a[x][1]+f[i][1];
			if (e>=0&&r>=0&&e<=301&&r<=301&&q[e][r]>a[x][2]+1)
			{
				mo++;
				a[mo][0]=e;
				a[mo][1]=r;
				a[mo][2]=a[x][2]+1;
				q[e][r]=-1;
			}
			if (e>=0&&e<=301&&r<=301&&r>=0&&q[e][r]==100000)
			{
				cout<<a[x][2]+1;
				answer=1;
				exit(0);
			}
		}
	}
}