Meteor Shower POJ - 3669 （bfs+优先队列）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=304;

int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int maze[maxn][maxn];
int vis[maxn][maxn];

struct node
{
    int x,y,step;
}temp,a;
bool operator < (const node &a,const node &b)
{
    return a.step>b.step;
}

int min(int a,int b)
{
    return a>b?b:a;
}
void bfs()
{
    int i;
    memset(vis,0,sizeof(vis));
    priority_queue<node>q;
    a.x=0; a.y=0;
    a.step=0;
    q.push(a);
    vis[0][0]=1;
    while(!q.empty())
    {
        a=q.top();
        q.pop();
        if(maze[a.x][a.y]==-1)
        {
            cout<<a.step<<endl;
            return ;
        }
        for(i=0;i<4;i++)
        {
            temp.x=a.x+dx[i];
            temp.y=a.y+dy[i];
            temp.step=a.step+1;
            if(temp.x>=0 && temp.y>=0 && (maze[temp.x][temp.y]==-1 || maze[temp.x][temp.y]>temp.step))
            {
                if(!vis[temp.x][temp.y])
                    q.push(temp);
                vis[temp.x][temp.y]=1;
            }
        }
        
    }
    cout<<-1<<endl;
    
    
}

int main()
{
    int n,x,y,t;
    memset(maze,-1,sizeof(maze));
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x>>y>>t;
        if(maze[x][y]==-1)
            maze[x][y]=t;
        else
            maze[x][y]=min(maze[x][y],t);
        for(int j=0;j<4;j++)
        {
            int nx=x+dx[j];
            int ny=y+dy[j];
            if(nx>=0 && ny>=0)
            {
              if(maze[nx][ny]==-1)
                  maze[nx][ny]=t;
              else
                  maze[nx][ny]=min(t,maze[nx][ny]);
            }
        }
        
    }
    bfs();
    return 0;
}