threeKingdom(dijska)

#include <iostream>
#define maxN 1005
#define INF 1e9

using namespace std;
int s, n, m, k, T, numLand;
int map[maxN][maxN];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int mapValue[8] = {1, 3, 5, -1, 3, -1, 3, -1};

int d[maxN][maxN];
bool visit[maxN][maxN];

struct Kingdom {
	int numC;
	int x[maxN];
	int y[maxN];
} kings[maxN];

void dijkstra() {

	for (int i=0; i<numLand; i++) {
		int Max = INF;
		int x = -1, y = -1;
		for (int i=1; i<=s; i++) 
			for (int j=1; j<=s; j++)
			if (d[i][j] < Max && !visit[i][j]) {
				x = i;
				y = j;
				Max = d[i][j];
			}
		if (x != -1) {
			visit[x][y] = true;
			for (int i=0; i<4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (0<nx && nx<=s && 0<ny && ny<=s && map[nx][ny]!=-1) {
					int newDis = (map[x][y] + map[nx][ny]) + d[x][y];
					if (newDis < d[nx][ny]) d[nx][ny] = newDis;
				}
			}
		}

	}

}


void reset() {
	int i = 0;
	for (int i=1; i<=s; i++) 
		for (int j=1; j<=s; j++){
			d[i][j] = INF;
			visit[i][j] = false;
		}

	for (int j=0; j<kings[i].numC; j++) {
		d[kings[i].x[j]][kings[i].y[j]] = 0;
		//visit[kings[i].x[j]][kings[i].y[j]] = true;
	}
	numLand = s*s;
}


int main() {
	freopen("inp.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	cin>>T;
	for (int tc=1; tc<=T; tc++) {
		cin>>s;
		cin>>n;
		for (int i=0; i<n; i++) {
			cin>>kings[i].numC;
			for (int j=0; j<kings[i].numC; j++) {
				cin>>kings[i].x[j]>>kings[i].y[j];
			}

		}
		int tmp, res;
		for (int i=1; i<=s; i++) 
		for (int j=1; j<=s; j++){
			cin>>tmp;
			map[i][j] = mapValue[tmp];
		}
		reset();
		dijkstra();

		cout<<'#'<<tc<<' '<<endl;
		/*for (int i=1; i<=s; i++) {
		for (int j=1; j<=s; j++){
			cout<<d[i][j]<<' ';
		}
		cout<<endl;
		}*/
		for (int i=1; i<n; i++) {
			res = 0;
			for (int j=0; j<kings[i].numC; j++) {
				res += d[kings[i].x[j]][kings[i].y[j]];
			}
			cout<<res/2<<' ';
		}
		cout<<endl;
	}
	return 0;
}