为什么是35分!!测试是读入有问题,但是我找不到......

P2895 [USACO08FEB] Meteor Shower S

Ay2024_4202yA @ 2024-12-17 18:45:20

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+5;
struct point{
    int x,y,step;
};
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
int m;
int f[305][305];
int vis[305][305];
queue<point> q;
int main(){
    for(int i=0;i<=300;i++){
        for(int j=0;j<=300;j++){
            f[i][j]=1e9;
        }
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        f[a][b]=min(c,f[a][b]);
        for(int j=0;j<4;j++){ 
            if(a+dx[j]<0||b+dy[j]<0)continue;
            f[a+dx[j]][b+dy[j]]=min(f[a+dx[j]][b+dy[j]],f[a][b]);
        }
    }/*
    for(int i=0;i<=6;i++){
        for(int j=0;j<=6;j++){
            cout<<setw(10)<<f[i][j]<<' ';
        }
        cout<<endl;
    }*/
    point s;
    s.x=0;s.y=0;s.step=0;
    q.push(s);
    while(!q.empty()){
        point n=q.front();
        q.pop();
        vis[n.x][n.y]=true;
        if(f[n.x][n.y]==1e9){
            cout<<n.step<<endl;
            return 0;
        }if(f[n.x][n.y]<=n.step){
            continue;
        }
        //cout<<n.x<<' '<<n.y<<' '<<n.step<<"\n";
        for(int i=0;i<4;i++){
            int nx=n.x+dx[i];
            int ny=n.y+dy[i];
            if(nx<0||ny<0||vis[nx][ny])continue;
            point d;
            d.x=nx;d.y=ny;d.step=n.step+1;
            q.push(d);
        }
    }cout<<-1<<endl;
    return 0;
}

|