记录编号	122301	评测结果	AAAAAAAAAAAAAA
题目名称	[USACO Feb08] 流星雨	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.042 s
提交时间	2014-09-23 08:59:35	内存使用	1.51 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <set>
#include <list>
#include <iterator>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <functional>
#include <deque>
#define For(i,j,k) for(int i=(j);i<=(k);i++)
using namespace std;
typedef long long LL;
typedef unsigned int Uint;
const int INF=0x7ffffff;
using namespace std;
//================struct declaration======================
struct node
{
  int time,x,y;
  node (int x=0,int y=0,int time=0):time(time),x(x),y(y){}
};
//================var declaration=-========================
const int MAXN=500;
int des[MAXN][MAXN],m;
bool vis[MAXN][MAXN];
int mvx[]={0,1,0,-1};
int mvy[]={1,0,-1,0};
queue <node> Q;
//================function declaration====================

//================main code===============================
int main()
{
  string ProgrammeName="meteor";
  string FloderName="COGS";
  freopen((ProgrammeName+".in").c_str(),"r",stdin);
  freopen((ProgrammeName+".out").c_str(),"w",stdout);
#ifdef DEBUG
  clock_t Start_Time=clock();
  system(("copy C:\\Users\\abc\\Desktop\\HouJikan\\"+FloderName+"\\standard.cpp C:\\Users\\abc\\Desktop\\HouJikan\\"+FloderName+"\\submit.txt").c_str());
#endif 
  scanf("%d",&m);
  memset(des,-1,sizeof(des));
  memset(vis,false,sizeof(vis));
  vis[0][0]=true;
  while (m--)
  {
    int x,y,t;
    scanf("%d%d%d",&x,&y,&t);
    if (des[x][y]==-1||des[x][y]>t)
      des[x][y]=t;
    if (x!=0&&(des[x-1][y]==-1||des[x-1][y]>t))
      des[x-1][y]=t;
    if ((des[x+1][y]==-1||des[x+1][y]>t))
      des[x+1][y]=t;
    if (y!=0&&(des[x][y-1]==-1||des[x][y-1]>t))
      des[x][y-1]=t;
    if ((des[x][y+1]==-1||des[x][y+1]>t))
      des[x][y+1]=t;
  } 
  Q.push(node(0,0,0));
  while (!Q.empty())
  {
    int x=Q.front().x,y=Q.front().y,t=Q.front().time;
    Q.pop();
    if (des[x][y]==-1)
    {
      printf("%d\n",t);
      return 0;
    }
    For(i,0,3)
    {
      int xx=x+mvx[i],yy=y+mvy[i];
      if (xx<0||yy<0||vis[xx][yy]) continue;
      if (des[xx][yy]!=-1&&des[xx][yy]<=t+1) continue;
      Q.push(node(xx,yy,t+1));
      vis[xx][yy]=true; 
    }
  }
  printf("-1\n");
#ifdef DEBUG
  clock_t End_Time=clock();
  printf("\n\nTime Used :%.6lf Ms\n",double(Start_Time-End_Time)/(-CLOCKS_PER_SEC));
#endif
  return 0;
}
//================function code===========================