求助,63分,其余MLE

P2895 [USACO08FEB] Meteor Shower S

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

和我一样欸


|