RE

P2895 [USACO08FEB] Meteor Shower S

0LCH0 @ 2024-01-19 08:37:22

#include<bits/stdc++.h>
using namespace std;
int dis[501][501],dx[5]={0,0,1,0,-1},dy[5]={0,1,0,-1,0},g[501][501],ux,uy,vx,vy;
int n,m;
bool check(int x,int y){
    if(x<1||y<1||x>400||dis[x][y]!=-1)
        return 0;
}
int bfs(int x,int y)
{
    queue<int>qx,qy;
    qx.push(x);
    qy.push(y);
    dis[x][y]=0;
    int rx,ry;
    while(!qx.empty()){
        rx = qx.front();
        qx.pop();
        ry = qy.front();
        qy.pop();
        if(g[ux][uy]=0x3f3f3f3f)
            return dis[ux][uy];
        for(int i=1,tx,ty;i<=4;i++){
            vx = ux +dx[i];
            vy = uy +dy[i];
            if(check(vx,vy)&&g[vx][vy]>dis[ux][uy]+1){
                dis[vx][vy]=dis[ux][uy]+1;
                qx.push(vx);
                qy.push(vy);
            }
        }
    }
    return -1;
}
int main()
{
    cin>>m;
    memset(dis,-1,sizeof(dis));
    memset(g,0x3f,sizeof(g));
    for(int i=1,u,v,t;i<=m;i++){
        cin>>u>>v>>t;
        u=u+1;
        v=v+1;
        for(int j=0;i<5;j++)
            g[u+dx[j]][v+dy[j]]=min(g[u+dx[j]][v+dy[j]],t);
    }
    cout<<bfs(1,1);
    return 0;
}

|