HDU 5253 연결 파이프 (bfs + 우선 대기 열)

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=5253
광 수, 일반 우선 대기 열 광 수 와 는 다 르 니 코드 를 구체 적 으로 보 세 요.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int N, M;
struct node {
	int x, y, cost;
	friend bool operator < (node a, node b) {
		return a.cost > b.cost;  //     
	}
};
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
int map[1010][1010];
int vis[1010][1010];
int main() {
	int T;
	scanf("%d", &T);
	int kase;
	for(kase = 1; kase <= T; kase++) {
		scanf("%d %d", &N, &M);
		int i, j;
		for(i = 1; i <= N; i++) {
			for(j = 1; j <= M; j++) {
				scanf("%d", &map[i][j]);
			}
		}
		memset(vis, 0, sizeof(vis));
		priority_queue<node> q;
		node now, next;
		now.x = 1, now.y = 1, now.cost = 0;
		q.push(now);
		int tot = N * M;  //    ，      
		int minc = 0;
		printf("Case #%d:
", kase);
		while(!q.empty()) {
			now = q.top();
			q.pop();
			if(vis[now.x][now.y] == 1) continue;  //           
			tot--;
			vis[now.x][now.y] = 1;
			minc += now.cost;
			if(tot == 0) {
				printf("%d
", minc);
				break;
			}
			for(i = 0; i < 4; i++) {
				next.x = now.x + dir[i][0];
				next.y = now.y + dir[i][1];
				if(next.x < 1 || next.x > N || next.y < 1 || next.y > M || vis[next.x][next.y] == 1) {
					continue;
				}
				next.cost = abs(map[next.x][next.y] - map[now.x][now.y]);
				q.push(next);
			}
		}
	}
	return 0;
}