4485:

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N;
int map[3][3];
int sum = 0;
int direct[4][2] = {
	-1,0,
	1,0,
	0,-1,
	0,1
};
struct Node {
	int y,x;
	int weight;
};
const int MAX = 21e8;
int result[3][3];
bool operator<(Node v, Node t) {
	return t.weight < v.weight;
}
priority_queue<Node>q;
int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			result[i][j] = MAX;
		}
	}
	q.push({ 0,0,map[0][0]});
	while (!q.empty()) {
		Node now = q.top();
		q.pop();
		if (result[now.y][now.x] < now.weight)continue;
		for (int t = 0; t < 4; t++) {
			int ny = now.y + direct[t][0];
			int nx = now.x + direct[t][1];
			if (nx < 0 || ny < 0 || ny >= 3 || nx >= 3)continue;
			int total = now.weight + map[ny][nx];

			if (result[ny][nx] > total) {
				result[ny][nx] = total;
				q.push({ ny,nx,total });
			}
		}
	}

	return 0;
}