震惊,某蒟蒻bfs竟然tle

P2895 [USACO08FEB] Meteor Shower S

Xhesika_Frost @ 2019-09-08 14:18:26

哪位好心的大佬给看看吧

safe记录是否安全

t记录最早被炸

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int safe[305][305];
int t[305][305];
int m;
int mx[5]={1,-1,0,0};
int my[5]={0,0,1,-1};
int xi,yi,ti;
struct b{
    int x;
    int y;
    int tim;
};
int vis[305][305];
queue <b> q;
int f;
b l;
void bfs(){
    while(q.size()){
        int nx=q.front().x;
        int ny=q.front().y;
        int nt=q.front().tim;
        vis[nx][ny]=1;
        q.pop();
        if(!safe[nx][ny]){
            cout<<nt;
            return ;
        }
        for(int i=0;i<=3;++i){
            int vx=nx+mx[i];
            int vy=ny+my[i];
            if(vx>=0&&vy>=0)
            if(nt+1<t[vx][vy])
                {
                    if(!vis[vx][vy])
                    {
                        l.x=vx;
                        l.y=vy;
                        l.tim=nt+1;
                        q.push(l);
                        //q.push(vx,vy,nt+1{b})
                    }
                }
        }
    }
    cout<<-1;
    return ;
}
int main(){
    memset(t,0x3f,sizeof(t));
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&xi,&yi,&ti);
        t[xi][yi]=min(ti,t[xi][yi]);
        safe[xi][yi]=1;
        for(int j=0;j<=3;++j){
            if(xi+mx[j]>=0&&yi+my[j]>=0){
            t[xi+mx[j]][yi+my[j]]=min(t[xi+mx[j]][yi+my[j]],ti);
            safe[xi+mx[j]][yi+my[j]]=1;
        }
        }
    }
    l.x=l.y=l.tim=0;
    q.push(l);
    bfs();
    return 0;
} 

by Li_zi_wei @ 2019-09-08 14:29:56

去你的蒟蒻


by dingcx @ 2020-01-28 13:58:00

@For_Miku 在bfs中的q.push(l)前面加一个vis[vx][vy]=1就能过。

和提问时间离得好远


by Xhesika_Frost @ 2020-01-28 15:02:57

@dingcx 谢谢,这么长时间蒟蒻一直没Aqwq


by wzmzmhk @ 2021-07-20 00:13:36

@dingcx 感谢大佬!我也是

考古


by liangbowen @ 2021-11-03 12:20:26

@dingcx 感谢大佬!我也是

保持队形


|