记录编号	333857	评测结果	AAAAAAAAAAAAAA
题目名称	138.[USACO Feb08] 流星雨	最终得分	100
用户昵称	traceback	是否通过	通过
代码语言	C++	运行时间	0.048 s
提交时间	2016-10-31 16:05:58	内存使用	0.70 MiB

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int,int> P;
const int inf=0x3f3f3f3f;
int killed[305][305];
int m;
int dx[]={0,0,-1,1},dy[]={1,-1,0,0};
struct S {
	int x,y,t;
}tmp;
bool vis[305][305];
void bfs() {
	if (killed[0][0]==0) {
		printf("-1\n");
		return;
	}
	queue<S> que;
	que.push(tmp);
	vis[0][0]=true;
	while (!que.empty()) {
		S v=que.front();que.pop();
		if (killed[v.x][v.y]>=inf) {
			printf("%d\n",v.t);
			return;
		}
		for (int i=0;i<4;i++) {
			int x2=v.x+dx[i],y2=v.y+dy[i];
			if (x2>=0&&y2>=0&&!vis[x2][y2]&&killed[x2][y2]>v.t+1) {
				tmp.x=x2;
				tmp.y=y2;
				tmp.t=v.t+1;
				vis[x2][y2]=true;
				que.push(tmp);
			}
		}
	}
	printf("-1\n");
}
int main() {
	freopen("meteor.in","r",stdin);
	freopen("meteor.out","w",stdout);
	memset(killed,0x3f,sizeof(killed));
	scanf("%d",&m);
	int a,b,c;
	for (int i=1;i<=m;i++) {
		scanf("%d%d%d",&a,&b,&c);
		killed[a][b]=min(killed[a][b],c);
		for (int j=0;j<4;j++) {
			int x=a+dx[j],y=b+dy[j];
			if (x>=0&&y>=0) killed[x][y]=min(killed[x][y],c);
		}
	}
	bfs();
	return 0;
}