[c++]#10-#14 MLE 求助大佬

P2895 [USACO08FEB] Meteor Shower S

D_guard @ 2022-05-12 18:00:49

rt,蒟蒻代码如下:

#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#define stn frm[x+trn[i][0]+1][y+trn[i][1]+1]
#define nxtx x.x+trn[i][0]
#define nxty x.y+trn[i][1]
using namespace std;

int m, x, y, t, frm[303][303];
int trn[5][2] = {0,0,-1,0,1,0,0,-1,0,1};
struct pos{
    int x, y, t;
} stt;
queue<pos> q;

int bfs(pos x){
    if(frm[x.x][x.y]==50001)    return x.t-1;                   
    frm[x.x][x.y] = -1;
    for(int i=1; i<5; ++i){
        if(frm[nxtx][nxty]<=x.t)    continue;
        if(nxtx<1 || nxtx>301 || nxty<1 || nxty>301)    continue;
        pos y{nxtx, nxty, x.t+1};   
        q.push(y);
    }
    if(q.size()==0) return -1;
    pos y = q.front();  q.pop();
    return bfs(y);      
}

int main(){
    for(int i=1; i<302; ++i)
        for(int j=1; j<302; ++j)
            frm[i][j] = 50001;
    scanf("%d", &m);
    while(m--){
        scanf("%d%d%d", &x,&y,&t);
        for(int i=0; i<5; ++i)  stn = min(stn, t);
    }
    stt.x = stt.y = stt.t = 1;
    printf("%d", bfs(stt));
    return 0;
}

by codeG0d @ 2022-06-03 19:15:29

同求,请问lz解决了么?谢谢


by D_guard @ 2022-09-15 17:36:22

@codeG0d 最近抽空回来做这个题,这个问题应该是队列空间用太多了,改成先判定再入队就行......


|