백준 4485: 녹색 옷 입은 애가 젤다지?

#include <iostream>
#include <cstring> // memset
#include <vector>
#include <utility> // pair
#include <queue> // pq
#define INF 0x7FFFFFFF
#define MAX 126
using namespace std;

int weight[MAX][MAX];
int dist[MAX][MAX];
bool visited[MAX][MAX];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int T, N, i, j, tmpWeight, newWeight, nowR, nowC;
	priority_queue< pair< int, pair<int, int> >, vector< pair< int, pair<int, int> > >, greater< pair< int, pair<int, int> > > > pq; // (cost, (row, col))

	T = 0;

	while (true) {
		memset(visited, false, sizeof(visited));

		cin >> N;
		if (N == 0) break;

		for (i = 1; i <= N; i++) {
			for (j = 1; j <= N; j++) {
				cin >> weight[i][j];
				dist[i][j] = INF;
			}
		}

		nowR = nowC = 1;
		dist[nowR][nowC] = weight[nowR][nowC];
		pq.push(make_pair(dist[nowR][nowC], make_pair(nowR, nowC)));

		while (!pq.empty()) {
			tmpWeight = pq.top().first;
			nowR = pq.top().second.first;
			nowC = pq.top().second.second;
			pq.pop();

			if (!visited[nowR][nowC]) {
				visited[nowR][nowC] = true;

				if (nowR - 1 >= 1) { // UP
					newWeight = tmpWeight + weight[nowR - 1][nowC];
					if (newWeight < dist[nowR - 1][nowC]) dist[nowR - 1][nowC] = newWeight;
					if (!visited[nowR - 1][nowC]) pq.push(make_pair(dist[nowR - 1][nowC], make_pair(nowR - 1, nowC)));
				}

				if (nowR + 1 <= N) { // DOWN
					newWeight = tmpWeight + weight[nowR + 1][nowC];
					if (newWeight < dist[nowR + 1][nowC]) dist[nowR + 1][nowC] = newWeight;
					if (!visited[nowR + 1][nowC]) pq.push(make_pair(dist[nowR + 1][nowC], make_pair(nowR + 1, nowC)));
				}

				if (nowC - 1 >= 1) { // LEFT
					newWeight = tmpWeight + weight[nowR][nowC - 1];
					if (newWeight < dist[nowR][nowC - 1]) dist[nowR][nowC - 1] = newWeight;
					if (!visited[nowR][nowC - 1]) pq.push(make_pair(dist[nowR][nowC - 1], make_pair(nowR, nowC - 1)));
				}

				if (nowC + 1 <= N) { // RIGHT
					newWeight = tmpWeight + weight[nowR][nowC + 1];
					if (newWeight < dist[nowR][nowC + 1]) dist[nowR][nowC + 1] = newWeight;
					if (!visited[nowR][nowC + 1]) pq.push(make_pair(dist[nowR][nowC + 1], make_pair(nowR, nowC + 1)));
				}
			}
		}
		T++;
		cout << "Problem " << T << ": " << dist[N][N] << endl;
	}
	return 0;
}