求助为什么过不了

P2895 [USACO08FEB] Meteor Shower S

asd1926 @ 2021-07-24 15:23:39

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;

const int N = 5e3 + 10;

int m;
int dist[1000][1000];
int time1[1000][1000];
bool st[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int bfs () {
    queue<PII> q;
    memset (dist, 0x3f, sizeof dist);
    q.push({0, 0});
    dist[0][0] = 0;
    if (time1[0][0] == 0) return -1;
    st[0][0] = true;
    while(q.size()) {
        auto t = q.front(); q.pop();
        int x = t.first, y = t.second;
        if (time1[x][y] == 0x3f3f3f3f) return dist[x][y];
        for (int i = 0; i < 4; i ++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx > 300 || ny < 0 || ny > 300) continue;
            if (st[nx][ny]) continue;
            int d = dist[x][y] + 1;
            if (d >= time1[nx][ny]) continue;

            st[nx][ny] = true;
            dist[nx][ny] = d;
            q.push({nx, ny});
        }
    }
    return -1;
}
int main () {
    cin >> m;
    memset (time1, 0x3f, sizeof time1);
    for (int i = 0; i < m; i ++) {
        int x, y, t;
        cin >> x >> y >> t;
        time1[x][y] = t;
        if (x >= 1) time1[x - 1][y] = t;
        if (x < 300) time1[x + 1][y] = t;
        if (y >= 1) time1[x][y - 1] =t;
        if (y < 300) time1[x][y + 1] = t;
    }
    cout << bfs() << endl;

    return 0;
}

by asd1926 @ 2021-07-24 15:36:58

已解决


|