大佬们,最后五个点mle了,望指教,谢谢大佬们

P2895 [USACO08FEB] Meteor Shower S

JunBuJian @ 2022-03-17 09:44:27

#include<iostream>
#include<queue>
#include<cstring>

#define x first
#define y second

using namespace std;
typedef pair<int,int> PII;
const int N = 410;
int t[N][N],d[N][N];
bool st[N][N];

int n;
int dx[] = {1,-1,0,0},dy[] = {0,0,1,-1};

int bfs()
{
    queue<PII> q;
    q.push({0,0});

    memset(d,-1,sizeof d);

    d[0][0] = 0;

    while(q.size())
    {
        auto h = q.front();
        q.pop();

        for(int i = 0;i < 4;i ++)
        {
            int x = h.x + dx[i];
            int y = h.y + dy[i];

            if(x < 0 || y < 0 || x > 300 || y > 300) continue;// 边界
            if(t[x][y] != 10000 && d[h.x][h.y]  + 1 >= t[x][y]) continue;

            d[x][y] = d[h.x][h.y] + 1;

            if(t[x][y] == 10000) return d[x][y];

            q.push({x,y});

        }
    }

    return -1;
}
int main()
{
    cin >> n;

    for(int i = 0;i <= 300;i ++) 
       for(int j = 0;j <= 300;j ++)
          t[i][j] = 10000;

    int a,b,m;
    while(n --)
    {
        cin >> a >> b >> m;

        if(st[a][b]) t[a][b] = min(t[a][b],m);
        else 
        {
            t[a][b] = m;
            st[a][b] = true;
        }    

        //预处理陨石掉落时间和范围
        for(int i = 0;i < 4;i ++)
        {
            int x = a + dx[i];
            int y = b + dy[i];

        if(x < 0 || y < 0 || x > 300 || y > 300) continue;
        if(st[x][y]) t[x][y] = min(t[x][y],m);
        else 
        {
            t[x][y] = m;
            st[x][y] = true;
        } 
        }
    }

    cout << bfs() << endl;

}

|