toroso @ 2020-07-17 23:56:04
#pragma GCC optimize(3)
#pragma GCC optimize(2)
#include<stdio.h>
#include<cstring>
#include<queue>
using namespace std;
inline int read(){
int k=0,j=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')j=-1;c=getchar();}
while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
return k*j;
}
struct pp2{int jx,jy;};queue<pp2>c;
int a[305][305],ans[305][305];
int main(){
memset(a,0,sizeof(a));
int m=read();
for(int i=1;i<=m;i++){
int j1=read(),j2=read(),t=read();
if(t==0)t=-1;
if(a[j1][j2]==0||a[j1][j2]>t)
a[j1][j2]=t;
if(j1<=310)
if(a[j1+1][j2]==0||t<a[j1+1][j2])
a[j1+1][j2]=t;
if(j1>=1)
if(a[j1-1][j2]==0||t<a[j1-1][j2])
a[j1-1][j2]=t;
if(j2<=310)
if(a[j1][j2+1]==0||t<a[j1][j2+1])
a[j1][j2+1]=t;
if(j2>=1)
if(a[j1][j2-1]==0||t<a[j1][j2-1])
a[j1][j2-1]=t;
}
c.push((pp2){0,0});
while(!c.empty()){
int i=c.front().jx,j=c.front().jy;
c.pop();
if(a[i][j]==0){printf("%d",ans[i][j]);return 0;}
if(i<311&&(a[i+1][j]==0||a[i+1][j]>ans[i][j]+1)){
c.push((pp2){i+1,j});ans[i+1][j]=ans[i][j]+1;
}
if((a[i-1][j]==0||a[i-1][j]>ans[i][j]+1)&&i>=1){
c.push((pp2){i-1,j});ans[i-1][j]=ans[i][j]+1;
}
if(j<311&&(a[i][j+1]==0||a[i][j+1]>ans[i][j]+1)){
c.push((pp2){i,j+1});ans[i][j+1]=ans[i][j]+1;
}
if((a[i][j-1]==0||a[i][j-1]>ans[i][j]+1)&&j>=1){
c.push((pp2){i,j-1});ans[i][j-1]=ans[i][j]+1;
}a[i][j]=-1;
}
printf("-1");
return 0;
}
by 刘芝麻 @ 2020-07-18 00:26:44
看不懂啊
by Liu45318 @ 2020-07-18 09:20:11
不是mle吗用这么多时间优化干什么
by toroso @ 2020-07-18 14:15:57
@Liu45318如果不用时间优化,就会1~2个点TLE
by xiaoyu20070727 @ 2020-07-22 17:19:14
和我一样欸