记录编号	283838	评测结果	AAAAAAAAAAAAAA
题目名称	[USACO Feb08] 流星雨	最终得分	100
用户昵称	@@@	是否通过	通过
代码语言	C++	运行时间	0.063 s
提交时间	2016-07-15 19:16:28	内存使用	49.14 MiB

//{==============套路========================//
#include <fstream>
#include <queue>
#define inf 99999999
using namespace std;
ifstream cin("meteor.in");
ofstream cout("meteor.out");
//}=================================//
//{==============全局变量====================//
int e[3200][3200],now=0;
bool book[3200][3200];
int t[5][3]={{0,0,0},{0,-1,0},{0,0,1},{0,1,0},{0,0,-1}};
int m;
//}================//
//{==============CLASS=======================//
class point
{
public:
	int x,y,TIME;
	point(int _x,int _y,int _TIME)
	{
		x=_x;
		y=_y;
		TIME=_TIME;
	}

	point()
	{}
};
//}=========================//
//{==============QUEUE=======================//
queue <point> q;
//}================BFS=====================//

//{==============BFS=========================//
int bfs()
{
	point a(0,0,0);
	q.push(a);
	
	book[0][0]=1;
	while(!q.empty())
	{
		point h=q.front(),new_;
		q.pop();
		if(e[h.x][h.y]==inf)
		{
			return h.TIME;
		}
		if(e[h.x][h.y]<=h.TIME)
		{
			continue;
		}
		for(int k=1;k<=4;k++)
		{
			
			new_.x=h.x+t[k][1];
			new_.y=h.y+t[k][2];
			new_.TIME=h.TIME+1;
			//new_(h.x+t[k][1],h.y+t[k][2],h.TIME+1);
			if(new_.x>=0&&new_.y>=0&&new_.TIME<e[new_.x][new_.y])
				if(book[new_.x][new_.y]==0)
				{
					book[new_.x][new_.y]=1;
					q.push(new_);
				}
		}
	}
	
	return -1;
}
//}=====================================//
//{==============MAIN========================//
int main()
{	
	cin>>m;
	int i,t1,t2,t3,j,k;
	//========初始化============//
	for(i=0;i<=310;i++)
		for(j=0;j<=310;j++)
		{
			book[i][j]=0;
			e[i][j]=inf;
		}
	//========读入==============//
	for(i=1;i<=m;i++)
	{
		cin>>t1>>t2>>t3;
			for(k=0;k<=4;k++)
				if(e[t1+t[k][1]][t2+t[k][2]]>t3)
					e[t1+t[k][1]][t2+t[k][2]]=t3;
	}
	//========宽搜==============//
	cout<<bfs()<<endl;
	cin.close();
	cout.close();
	return 0;
}