大佬走过路过不要错过!

P2895 [USACO08FEB] Meteor Shower S

peppaking8 @ 2019-07-25 21:03:31

救救孩子。。。最后几个点TLE和MLE,请求大佬优化。。。

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int x,y;
    int step;
    bool operator < (const Node &x)const{
        return step>x.step;
    }
}t,nt;
int m;
int meet[305][305];
bool vis[305][305];
int pos[5][2]={0,0,0,1,0,-1,1,0,-1,0};
priority_queue<Node>q;
void bfs(){
    t.x=0,t.y=0,t.step=0;
    q.push(t);
    while(!q.empty()){
        t=q.top();
        q.pop();
        if(meet[t.x][t.y]==0x3f3f3f3f){
            printf("%d",t.step);
            return ;
        }
        for(int i=1;i<5;i++){
            nt.x=t.x+pos[i][0];
            nt.y=t.y+pos[i][1];
            nt.step=t.step+1;
            if(nt.x<0) continue;
            if(nt.y<0) continue;
            if(!vis[nt.x][nt.y]&&nt.step<meet[nt.x][nt.y]){
                q.push(nt);
            }
        }
    }
    printf("-1");
}
int main(){
    scanf("%d",&m);
    for(int i=0;i<=300;i++){
        for(int j=0;j<=300;j++){
            meet[i][j]=0x3f3f3f3f;
        }
    }
    for(int i=1;i<=m;i++){
        int x,y,t;
        scanf("%d%d%d",&x,&y,&t);
        for(int i=0;i<5;i++){
            int r1=x+pos[i][0];
            int r2=y+pos[i][1];
            if(r1<0||r2<0) continue;
            if(meet[r1][r2]>t) meet[r1][r2]=t;
        }
    }
    bfs();
    return 0;
}

QAQ


by wuyutong111 @ 2019-07-25 21:05:25

蒟蒻路过……


by peppaking8 @ 2019-07-25 21:12:20

简单的BFS啊,就是T了。。。求助!


by tythen @ 2019-07-25 21:15:15

简单的BFS不需要用priority_queue的,又不是最短路什么的(゜ロ゜)


by peppaking8 @ 2019-07-25 21:16:22

@tythen 就是把答案排个序嘛。。。


by peppaking8 @ 2019-07-25 21:16:44

是改成queue吗?


by tythen @ 2019-07-25 21:18:16

@用户未知 是的哦,因为BFS是按层搜索的,答案每一层是不需要排序的


by peppaking8 @ 2019-07-25 21:18:56

@tythen 提交了,MLE是没了,但是一堆T。。。


by tythen @ 2019-07-25 21:21:03

@用户未知 那么bfs写错了吧,你防止重复搜索的vis好像没用上吧


by peppaking8 @ 2019-07-25 21:22:11

知道了,脑抽了。。。大佬orz


by dingcx @ 2020-01-28 13:59:45

orz AKIOI的大佬wxb %%%


|