RainsAFO @ 2019-09-28 15:13:39
#include<bits/stdc++.h>
using namespace std;
struct node {
int x,y,t;
} star;
int ti[601][601],x[50001],y[50001],t[50001];
bool f[5001][5001];
int m;
int dx[5]= {0,1,0,-1,0},dy[5]= {0,0,1,0,-1};
int main() {
cin>>m;
memset(ti,0x3f,sizeof(ti));
for(int i=1; i<=m; i++)
cin>>x[i]>>y[i]>>t[i];
for(int i=1; i<=m; i++)
for(int j=0; j<5; j++) {
int px=x[i]+dx[j],py=y[i]+dy[j];
if(ti[px][py]>=t[i])
ti[px][py]=t[i];
}
if(ti[0][0]==1061109567) {
cout<<0;
return 0;
}
int ans=0x7fffffff;
queue<node>q;
star.x=0,star.y=0,star.t=1;
q.push(star);
f[0][0]=1;
while(!q.empty()) {
node n=q.front();
q.pop();
for(int i=1; i<5; i++) {
int px=n.x+dx[i],py=n.y+dy[i];
if(ti[px][py]) {
if(n.t>=ti[px][py])
continue;
}
if(px>=0&&py>=0&&px<=311&&py<=311&&ti[px][py]==1061109567) {
if(ans>n.t)
ans=n.t;
break;
}
if(px>=0&&py>=0&&px<=311&&py<=311&&!f[px][py]) {
f[px][py]=1;
star.x=px,star.y=py,star.t=n.t+1,q.push(star);
}
}
}
if(ans==0x7fffffff)
cout<<-1;
else
cout<<ans;
}
为什么数组开到600还RE啊
by RainsAFO @ 2019-09-28 15:22:35
Dev什么鬼,开1000跑不出来,交上去过了
by Reqwey @ 2019-09-28 21:10:51
大佬什么时候不打牌(DP)了,开始吹风扇(*FS)了?