P2895 [USACO08FEB] Meteor Shower S

有MLE，还有WA，得分28

代码：用BFS广搜路径，形成到每一步的时间（vis）

#include<bits/stdc++.h>
using namespace std;
const int N=410;
int n,vis[N][N],timei[N][N];
int X[10]={0,0,0,1,-1};
int Y[10]={0,1,-1,0,0};
struct node
{
	int x,y;
};
inline void BFS()
{
	memset(vis,-1,sizeof(vis));
	queue<node>q;
	vis[0][0]=0;
	q.push((node){0,0});
	while(q.empty()!=1)
	{
		node now=q.front();
		q.pop();
		for(int i=1;i<=4;i++)
		{
			int x_1=now.x +X[i],y_1=now.y +Y[i];
			if(x_1<0 || y_1<0)continue;
			if(timei[x_1][y_1]<=vis[now.x ][now.y ]+1 && timei[x_1][y_1]!=-1)continue;
			vis[x_1][y_1]=vis[now.x ][now.y ]+1;
			q.push((node){x_1,y_1});
			if(timei[x_1][y_1]==-1)return (void)(cout<<vis[x_1][y_1]);
		}
	}
	cout<<"-1";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	memset(timei,-1,sizeof(timei));
	for(int i=1;i<=n;i++)
	{
		int x,y,t;
		cin>>x;
		cin>>y;
		cin>>t;
		for(int j=0;j<=4;j++)
		{
			int xi=x+X[j],yi=y+Y[j];
			if(xi<0 || yi<0)continue;
			if(timei[xi][yi]==-1)timei[xi][yi]=t;
		}
	}
	BFS();
	return 0;
}