ZOJ2849 Attack of Panda Virus 熊貓燒香~~ 優先隊列+搜索

這題目很是坑爹，各種坑爹，一開始SF了不止多少次，後來發現是Type的不僅僅是1，2.而是到1000，還有給出的圖 是500 * 500的，可是直接去搜索一直超時，想不通，題目給的是3000ms，早就夠了可是不行，後來再改，又SF，不能忍了，就YY了一下，用優先隊列把

總是做算法，不如來個陶冶情操的文章一篇： http://www.sanwen.net/subject/3628849/

題意：

給出一個矩陣，每一個元素代表一台電腦，每台電腦有一個值，這個值為了區分題目要求是負的，代表它能夠抵御病毒幾天，已經被一種病毒感染的電腦不會再被其它病毒感染，但是它無法阻攔其它病毒去感染其它電腦，然後有兩種病毒｛1，2，3，....1000｝種的任意兩種，Type類型值小的先去感染，但是肯定不同種類，第一天有兩台電腦，病毒是可以傳染的，第一天只能感染抵御一天的電腦，第二天才能感染只能抵御2天以及2天以下的，第三天能感染只能抵御3天以及3天以下的電腦，所有電腦被感染後 會有 Q個提問， 每一個提問 會問你 此病毒 最終感染了幾台電腦

YY了一把優先隊列，因為搜索一直超時改了SF所以感覺就是要優化， 按題意 很明顯，抵御天數少的 放前面， 如果兩台電腦抵御天數一樣，病毒Type值小的 先去進行感染，這樣優先條件就好了，然後 搜索一下，又舉了 幾個案例 過了 就交了一把 發現 RE，感覺自己程序寫的沒問題 也不會爆棧，所以說這道題目坑， 他沒有明確的說明Q的范圍，但是如果你開的Q的數組小於10^6的話，就是RE，所以這道題目坑點 數不勝數

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long

using namespace std;

#define inf 10000000

int n,m;
int dir[4][2]={0,-1,0,1,1,0,-1,0};
int ans[5000000 + 5];
int mp[1000 + 5][1000 + 5];

void clear() {
	memset(ans,0,sizeof(ans));
	memset(mp,0,sizeof(mp));
}

typedef struct Node {
	int level;
	int type;
	int sx,sy;
	friend bool operator< (Node n1, Node n2) {
		if(n1.level == n2.level)
			return n1.type > n2.type;
		return n1.level > n2.level;
	}
};

priority_queue q; 

void dfs() {
	Node s,e;
	while(!q.empty()) {
		s = q.top();
		q.pop();
		int tmp = -inf;
		for(int i=0;i<4;i++) {
			int dx = s.sx + dir[i][0];
			int dy = s.sy + dir[i][1];
			if(dx <0 || dx >=n || dy<0 || dy>=m)continue;
			if(mp[dx][dy] > 0)continue;
			if(mp[dx][dy] + s.level >= 0) {
				e.sx = dx;
				e.sy = dy;
				e.type = s.type;
				ans[s.type]++;
				e.level = s.level;
				mp[dx][dy] = s.type;
				q.push(e);
			}
			else {
				if(mp[dx][dy] > tmp)
					tmp = mp[dx][dy];
			}
		}
		if(tmp != -inf) {
			s.level = -tmp;
			q.push(s);
		}
	}
}

int main() {
	while(scanf("%d %d",&n,&m) == 2) {
		clear();
		for(int i=0;i 0) {
					Node node;
					node.sx = i;
					node.sy = j;
					node.type = mp[i][j];
					node.level = 1;
					q.push(node);
					ans[mp[i][j]]++;
				}
			}
		}
		dfs();
		int Q;
		scanf("%d",&Q);
		for(int i=0;i