记录编号	403633	评测结果	AAAAAAAAAAAAAA
题目名称	[USACO Feb08] 流星雨	最终得分	100
用户昵称	white	是否通过	通过
代码语言	C++	运行时间	0.043 s
提交时间	2017-05-10 21:28:24	内存使用	1.26 MiB

#include<cstdio>   
#include<queue>  
using namespace std;  
struct node{  
    int x,y;  
    int step;  
}s_pos;  
int  map[333][333];  
int  cnt[333][333];  
bool vis[333][333];  
int m,flag,ans;  
int dx[]={1,-1,0,0};  
int dy[]={0,0,-1,1};  
bool check(int x,int y){  
    return x>=0&&x<=301&&y>=0&&y<=301;  
}  
void bfs(){  
    queue<node> q;  
    s_pos.x=0;
	s_pos.y=0;
	s_pos.step=0;  
    q.push(s_pos);  
    vis[0][0]=true;  
    while(!q.empty()){  
        node now=q.front();
		q.pop();  
        if(map[now.x][now.y]==-1)
		{  
            flag=1;  
            ans=now.step;  
            return;  
        }  
        for(int i=0;i<4;i++)
		{  
            node next=now;  
            next.x+=dx[i];
			next.y+=dy[i]; 
			next.step++;  
            if(check(next.x,next.y)&&!vis[next.x][next.y]&&  
               (next.step<map[next.x][next.y]||map[next.x][next.y]==-1))
			   {  
                vis[next.x][next.y]=true;  
                q.push(next);  
            }  
        }  
  
    }  
  
}  
int main(){ 
    freopen("meteor.in","r",stdin);  
    freopen("meteor.out","w",stdout);	
    int a,b,t;  
    scanf("%d",&m);  
    for(int i=0;i<=301;i++)
		for(int j=0;j<=301;j++)
			map[i][j]=-1;  
    for(int i=0;i<m;i++){  
       scanf("%d%d%d",&a,&b,&t);  
       if(map[a][b]==-1||t<map[a][b])  
       map[a][b]=t;  
       for(int j=0;j<4;j++)
	   {  
          int nx=a+dx[j]; 
		  int ny=b+dy[j];  
          if(check(nx,ny)&&(map[nx][ny]==-1||t<map[nx][ny]))
		  {  
			map[nx][ny]=t;  
          }  
       }  
    }  
    bfs();  
    if(flag)  
    printf("%d\n",ans);  
    else  
    printf("-1\n");  
    return 0;  
}