请问为什么用-1就是错的,用无穷大就是对的,百思不得解佬们

P2895 [USACO08FEB] Meteor Shower S

RingTouSou @ 2023-10-24 22:29:53

这是无穷大的代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

typedef pair<int, int> PII;

const int N=310;
#define x first
#define y second

int m;
int dist[N][N];
int fire[N][N];
PII q[N*N];

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

int bfs()
{
    q[0]={0,0};
    dist[0][0] = 0;
    int hh=0,tt=0;

    while(hh<=tt)
    {
        auto t=q[hh++];

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

        if(a<0||b<0)    continue;
        if(dist[a][b])    continue;
        if(dist[t.x][t.y]+1>=fire[a][b])    continue;

        dist[a][b] = dist[t.x][t.y] + 1;
        q[++tt]={a,b};

        if(fire[a][b]>1e9)  return dist[a][b];
    }
    }
    return -1;
}
int main()
{
    memset(fire,0x3f,sizeof fire);
    cin>>m;
    while(m--)
    {
        int x1,y1,t;
        cin>>x1>>y1>>t;
        fire[x1][y1]=min(t,fire[x1][y1]);
        for(int i=0;i<4;i++)
        {
            int a = x1 + dx[i];
            int b = y1 + dy[i];
            if(a<0||a>301||b<0||b>301)
            {
                continue;
             } 
            fire[a][b]=min(t,fire[a][b]);
        } 
    }
    int k=bfs();
    cout<<k;
    return 0;
}

这是-1的代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

typedef pair<int, int> PII;

const int N=310;
#define x first
#define y second

int m;
int dist[N][N];
int fire[N][N];
PII q[N*N];

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

int bfs()
{
    q[0]={0,0};
    dist[0][0] = 0;
    int hh=0,tt=0;

    while(hh<=tt)
    {
        auto t=q[hh++];

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

        if(a<0||b<0)    continue;
        if(dist[a][b])    continue;
        if(dist[t.x][t.y]+1>=fire[a][b])    continue;

        dist[a][b] = dist[t.x][t.y] + 1;
        q[++tt]={a,b};

        if(fire[a][b]==-1)  return dist[a][b];
    }
    }
    return -1;
}
int main()
{
    memset(fire,-1,sizeof fire);
    cin>>m;
    while(m--)
    {
        int x1,y1,t;
        cin>>x1>>y1>>t;
        if(fire[x1][y1]==-1)
        {
            fire[x1][y1]=t;
        }
        for(int i=0;i<4;i++)
        {
            int a = x1 + dx[i];
            int b = y1 + dy[i];
            if(a<0||a>301||b<0||b>301)
            {
                continue;
             } 
            if(fire[a][b]==-1)
        {
            fire[a][b]=t;
        }
        } 
    }
    int k=bfs();
    cout<<k;
    return 0;
}

|