# XDOJ_1089_bfs+优先队列

http://acm.xidian.edu.cn/problem.php?id=1089

```#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

int n,m,nn,tt,a[105][2],sta[105][105],t[105][105],dir[4][2] = {-1,0,0,-1,1,0,0,1};
struct water
{
int x,y,d,t;
water(int _x,int _y,int _d,int _t):x(_x),y(_y),d(_d),t(_t){};
friend bool operator <(water X,water Y)
{
return X.t > Y.t;
}
};

void bfs(int x,int y)
{
priority_queue<water> q;
q.push(water(x,y,0,1));
q.push(water(x,y,1,1));
q.push(water(x,y,2,1));
q.push(water(x,y,3,1));
while(!q.empty())
{
water temp = q.top();
q.pop();
if(temp.t > tt) return;
int xx = temp.x+dir[temp.d][0],yy = temp.y+dir[temp.d][1];
if(xx < 1 || xx > n || yy < 1 || yy > m)    continue;
if(t[xx][yy] == temp.t)    continue;
if(sta[xx][yy] == 0)  q.push(water(xx,yy,temp.d,temp.t+1));
else if(sta[xx][yy] == 4)
{
sta[xx][yy] = 0;
t[xx][yy] = temp.t;
q.push(water(xx,yy,0,temp.t+1));
q.push(water(xx,yy,1,temp.t+1));
q.push(water(xx,yy,2,temp.t+1));
q.push(water(xx,yy,3,temp.t+1));
}
else    sta[xx][yy]++;
}
}

int main()
{
while(~scanf("%d%d%d%d",&n,&m,&nn,&tt))
{
memset(sta,0,sizeof(sta));
memset(t,0,sizeof(t));
for(int i = 1;i <= nn;i++)
{
int x;
scanf("%d%d%d",&a[i][0],&a[i][1],&x);
sta[a[i][0]][a[i][1]] = x;
}
int x,y;
scanf("%d%d",&x,&y);
bfs(x,y);
for(int i = 1;i <= nn;i++)
{
if(t[a[i][0]][a[i][1]] == 0)    printf("1 %d\n",sta[a[i][0]][a[i][1]]);
else    printf("0 %d\n",t[a[i][0]][a[i][1]]);
}
}
return 0;
}```

## hdu 4006 The kth great number(优先队列)

The kth great number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65768/65768 K (Java/Others) Total Submission(s): 6982    Accepted Submission(s): 2837 Problem Description Xiao Ming and Xiao Bao are playing a simple Numbers game. In a roun

## 优先队列比较符重载

#include <iostream> #include <queue> using namespace std; struct Node{ int x, y; friend bool operator<(Node a, Node b){ return a.x > b.x; //x最小的节点在队首 } }; int main(){ priority_queue<Node> PQ; Node temp = {2, 3}; PQ.push(temp); temp

## [ACM] hdu 1242 Rescue (BFS+优先队列)

Rescue Problem Description Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison. Angel's friends want to save Angel. Their task is:

## 1475 建设国家(优先队列)

1475 建设国家 基准时间限制:1 秒 空间限制:131072 KB 分值: 20 难度:3级算法题 小C现在想建设一个国家.这个国家中有一个首都,然后有若干个中间站,还有若干个城市. 现在小C想把国家建造成这样的形状:选若干(可以是0个)的中间站把他们连成一条直线,然后把首都(首都也是一个中间站)连在这一条直线的左端.然后每个点可以连一个城市,特别的是最右端的点可以连接两个城市. 现在有n个城市的规划供小C选择.但是,他们那儿的交通条件比较差,他们那儿一天是2*H个小时,每个城市里面的人每天

## Battle City BFS+优先队列

Battle City Many of us had played the game "Battle city" in our childhood, and some people (like me) even often play it on computer now. What we are discussing is a simple edition of this game. Given a map that consists of empty spaces, rivers,