求助~~~

P2895 [USACO08FEB] Meteor Shower S

tangguochao @ 2022-01-26 18:52:51

#include "bits/stdc++.h"
using namespace std;
const int N = 500;
int n = 0;
int v[N][N];
typedef struct {
    int x, y, tt;
} PII;
queue<PII>q;
int dx[]={-1,1,0, 0};
int dy[]={0, 0, 1, -1 };
const int inf = 0x7fffffff;
void bfs()
{
    while (!q.empty())
    {
        int x = q.front().x, y = q.front().y, t = q.front().tt;
        if(v[x][y] == inf)
        {
            cout << t;
            return;
        }
        q.pop();
        for(int i=0; i<=3; i++)
        {
            int ux = x + dx[i], uy = y + dy[i];
            if(ux>=0 && uy>=0)
                if (t + 1 < v[ux][uy])
                    q.push({ux, uy, t + 1});
        }
    }
    cout << -1;
}
int main()
{
    cin.tie(0);
    int m; cin >> m;
    fill(v[0], v[0] + N*N, inf);
    while (m--)
    {
        int x, y, t; cin >> x >> y >> t;
        v[x][y] = min(v[x][y], t);
        for(int i=0; i<=3; i++)
        {
            int ux = x + dx[i], uy = y + dy[i];
            if (ux >= 0 && uy >= 0)
                v[ux][uy] = min(v[ux][uy], t);
        }
    }
    q.push({0, 0, 0});
    bfs();
    return 0;
}

|