bfs70分求调，感谢！

Justin_love_coding @ 2024-05-11 08:14:12

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int INF = 0x7f;

int n;
int a[310][310]; // 存储流星的数据
int b[310][310]; // 存储走到某个点的时间
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};

int bfs()
{
    queue<PII> q;
    q.push({0, 0});
    while (q.size())
    {
        PII t = q.front();
        if (a[t.first][t.second] == INF)
        {
            return b[t.first][t.second];
        }
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int xx = t.first + dx[i], yy = t.second + dy[i];
            if (xx >= 0 && yy >= 0 && b[xx][yy] == -1 && b[t.first][t.second] + 1 < a[xx][yy])
            {
                q.push({xx, yy});
                b[xx][yy] = b[t.first][t.second] + 1;
            }
        }
    }
    return -1;
}

void init(int x, int y, int t)
{
    a[x][y] = min(t, a[x][y]);
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx >= 0 && yy >= 0)
            a[xx][yy] = min(t, a[xx][yy]);
    }
}

int main()
{
    cin >> n;
    int x, y, t;
    for (int i = 0; i < 305; i++)
    {
        for (int j = 0; j < 305; j++)
        {
            a[i][j] = INF;
        }
    }
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d%d", &x, &y, &t);
        init(x, y, t);
    }
    memset(b, -1, sizeof b);
    b[0][0] = 0;
    cout << bfs() << endl;
    return 0;
}

by Tim0509 @ 2024-05-11 08:27:28

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int INF = 0x7f7f7f7f;

int n;
int a[310][310]; // 存储流星的数据
int b[310][310]; // 存储走到某个点的时间
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};

int bfs()
{
    queue<PII> q;
    q.push({0, 0});
    while (q.size())
    {
        PII t = q.front();
        if (a[t.first][t.second] == INF)
        {
            return b[t.first][t.second];
        }
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int xx = t.first + dx[i], yy = t.second + dy[i];
            if (xx >= 0 && yy >= 0 && b[xx][yy] == -1 && b[t.first][t.second] + 1 < a[xx][yy])
            {
                q.push({xx, yy});
                b[xx][yy] = b[t.first][t.second] + 1;
            }
        }
    }
    return -1;
}

void init(int x, int y, int t)
{
    a[x][y] = min(t, a[x][y]);
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx >= 0 && yy >= 0)
            a[xx][yy] = min(t, a[xx][yy]);
    }
}

int main()
{
    cin >> n;
    int x, y, t;
    for (int i = 0; i < 305; i++)
    {
        for (int j = 0; j < 305; j++)
        {
            a[i][j] = INF;
        }
    }
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d%d", &x, &y, &t);
        init(x, y, t);
    }
    memset(b, -1, sizeof b);
    b[0][0] = 0;
    cout << bfs() << endl;
    return 0;
}

0x7f 太小了，换成 0x7f7f7f7f即可

by Tim0509 @ 2024-05-11 08:31:23

@Justin_love_coding

by Justin_love_coding @ 2024-05-11 08:45:32

@Tim0509 感谢！