记录编号	550125	评测结果	AAAAAAAAAAAAAA
题目名称	[USACO Feb08] 流星雨	最终得分	100
用户昵称	夜莺	是否通过	通过
代码语言	C++	运行时间	0.044 s
提交时间	2020-03-02 23:07:17	内存使用	3.89 MiB

#include<cstdio>
using namespace std;
const int MAXN=310;
long long a[MAXN][MAXN]={0};
bool have[MAXN][MAXN]={false};
int rx[5]={0,1,0,-1,0},
    ry[5]={0,0,1,0,-1};
struct node{
	int xi;
	int yi;
	int ti;
}dui[MAXN*MAXN];
int n,t,w=1,atime;
int bfs(){
	have[1][1]=true;
	dui[1].xi=dui[1].yi=1;
	if(a[1][1]==-1)
		return 0;
	do{
		t++;
		atime=dui[t].ti+1;
		for(int i=1;i<=4;i++){
			int xx=dui[t].xi+rx[i],yy=dui[t].yi+ry[i];
			if(!xx||!yy)continue;
			if(a[xx][yy]==-1)
				return atime;
			if(atime<a[xx][yy]){
				if(!have[xx][yy]){
					w++;
					dui[w].xi=xx;
					dui[w].yi=yy;
					dui[w].ti=atime;
					have[xx][yy]=true;
				}
			}
		}
	}while(t<w);
	return -1;
}
int main(){
	freopen("meteor.in","r",stdin);
	freopen("meteor.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<MAXN;i++)
		for(int j=1;j<MAXN;j++)
			a[i][j]=-1;
	for(int i=1,x,y,T;i<=n;i++){
		scanf("%d%d%d",&x,&y,&T);
		x++;
		y++;
		for(int i=0;i<=4;i++)
		if(a[x+rx[i]][y+ry[i]]==-1||a[x+rx[i]][y+ry[i]]>T)
			a[x+rx[i]][y+ry[i]]=T;
	}
	printf("%d",bfs());
	return 0;
}