记录编号	289452	评测结果	AAAAAAAAAAAAAA
题目名称	[USACO Feb08] 流星雨	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.033 s
提交时间	2016-08-04 20:46:25	内存使用	0.77 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
struct Node
{
    int x,y,t;
    Node(int a=0,int b=0,int c=0){ x=a,y=b,t=c;}
};
int map[310][310],n,x,y,t;
bool vis[310][310];
void Work(int x,int y,int t)
{
	if(map[x][y]==-1||map[x][y]>t)map[x][y]=t;
	if(map[x+1][y]==-1||map[x+1][y]>t)map[x+1][y]=t;
	if(map[x][y+1]==-1||map[x][y+1]>t)map[x][y+1]=t;
	if( x-1>=0 && ( map[x-1][y]==-1||map[x-1][y]>t ) )map[x-1][y]=t;
	if( y-1>=0 && ( map[x][y-1]==-1||map[x][y-1]>t ) )map[x][y-1]=t;
}
void bfs()
{
	queue<Node> q;
	q.push(Node(0,0,0));
	while(!q.empty())
	{
		Node node=q.front();q.pop();
		if(map[node.x][node.y]==-1){
			printf("%d\n",node.t);return;
		}
		for(int i=0;i<4;i++)
		{
			Node temp=node;
			temp.x+=dx[i];
			temp.y+=dy[i];
			temp.t++;
			int tx=temp.x,ty=temp.y,tt=temp.t;
			if(tx>=0&&ty>=0&&!vis[tx][ty])
			{
				if(map[tx][ty]==-1 || map[tx][ty]>tt )
                {
                    q.push(Node(tx,ty,tt));
                    vis[tx][ty]=1;
                }
			}
		}
	}
	puts("-1");
}
int main()
{
	freopen("meteor.in","r",stdin);freopen("meteor.out","w",stdout);
	scanf("%d",&n);
	memset(map,-1,sizeof(map));
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&x,&y,&t);
		Work(x,y,t);
	}
	bfs();
}