求助

P2895 [USACO08FEB] Meteor Shower S

chenxuanting @ 2020-10-25 09:57:37

 #include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef unsigned long long ll;
int m;
int x,y,t;
int safe[305][305];
int vis[305][305];
int dx[5]={1,-1,0,0,0};
int dy[5]={0,0,1,-1,0};
int ans=-1;
struct node
{
    int x,y,t;
};
void bfs()
{
    queue<node> q;
    q.push((node){0,0,0});
    vis[0][0]=1;
    while(!q.empty()){
        node cur=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int ax=dx[i]+cur.x;
            int ay=dy[i]+cur.y;
            if(ax<0||ay<0){
                continue;
            }
            if(safe[ax][ay]==0x3f){
                ans=cur.t+1;
                return;
            }
            if(safe[ax][ay]<=cur.t+1){
                continue;
            }
            if(vis[ax][ay]==1){
                continue;
            }
            vis[ax][ay]=1;
            q.push((node){ax,ay,cur.t+1});
        }
    }
} 
int main()
{
    cin>>m;
    memset(safe,0x3f,sizeof(safe));
    for(int i=1;i<=m;i++){
        cin>>x>>y>>t;
        for(int i1=0;i1<=4;i1++){
            int ax=dx[i1]+x;
            int ay=dy[i1]+y;
            if(ax<0||ay<0){
                continue;
            }
            if(safe[ax][ay]>t){
                safe[ax][ay]=t;
            }
        }
    }
    if(safe[0][0]==0){
        cout<<"-1";
        return 0;
    }
    bfs();
    cout<<ans;
    return 0;
}

by laihaochen @ 2020-10-25 10:39:34

/fad


by Snow_Dreams @ 2020-10-25 16:15:13

@chenxuanting 说一下具体问题?/qwq


by namelessgugugu @ 2020-10-26 18:20:43

safe[ax][ay]==0x3f改成==0x3f3f3f3f试试 (建议百度一下memset的用法


by chenxuanting @ 2020-10-27 23:39:32

我谔谔


|