範例程式碼 uva929

//uva929
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <queue>
using namespace std;

int N = 1000;
int INF = 100000000;
int g[1000][1000], cost[1000][1000];
int r, c;

struct node {
	int x, y, w;
	bool operator < (const struct node a) const {
	   return w > a.w;
	}
} tl;

void dij() {
	int a, b;
	bool vis[1000][1000];
	priority_queue <struct node> pq;
	memset(vis, 0, sizeof(vis));
	g[1][1] = cost[1][1];
	tl.x = tl.y = 1, tl.w = g[1][1];
	pq.push(tl);
	while (!pq.empty()) {
		tl = pq.top();
		pq.pop();
		a = tl.x, b = tl.y;
		if (vis[a][b])
			continue;
		vis[a][b] = true;
		if (a > 1 && !vis[a - 1][b] && g[a - 1][b] > g[a][b] + cost[a - 1][b]) {
			g[a - 1][b] = g[a][b] + cost[a - 1][b];
			tl.x = a - 1;
			tl.y = b;
			tl.w = g[a - 1][b];
			pq.push(tl);
		}
		if (a < r && !vis[a + 1][b] && g[a + 1][b] > g[a][b] + cost[a + 1][b]) {
			g[a + 1][b] = g[a][b] + cost[a + 1][b];
			tl.x = a + 1;
			tl.y = b;
			tl.w = g[a + 1][b];
			pq.push(tl);
		}
		if (b > 1 && !vis[a][b - 1] && g[a][b - 1] > g[a][b] + cost[a][b - 1]) {
			g[a][b - 1] = g[a][b] + cost[a][b - 1];
			tl.x = a;
			tl.y = b - 1;
			tl.w = g[a][b - 1];
			pq.push(tl);
		}
		if (b < c && !vis[a][b + 1] && g[a][b + 1] > g[a][b] + cost[a][b + 1]) {
			g[a][b + 1] = g[a][b] + cost[a][b + 1];
			tl.x = a, tl.y = b + 1, tl.w = g[a][b + 1];
			pq.push(tl);
		}
	}
}

int main() {
	int T, i, j;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &r, &c);
		for (i = 1; i <= r; ++i) {
			for (j= 1; j <= c; ++j) {
				scanf("%d", &cost[i][j]);
				g[i][j] = INF;
			}
		}
		dij();
		printf("%d\n", g[r][c]);
	}
	return 0;
}