[BOJ] 4485 : 녹색 옷 입은 애가 젤다지?

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int dx[] = { 0,0,-1,1 };
const int dy[] = { -1,1,0,0 };

int n, t, x, a[133][133], d[133][133];
struct abc {
    int x, y, c;
    bool operator <(abc a)const { return c > a.c; }
};

int main() {
    for (scanf("%d", &n); n; scanf("%d", &n)) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                scanf("%d", &a[i][j]);
                d[i][j] = 1e9;
            }
        }
        priority_queue<abc> pq;
        d[1][1] = a[1][1];
        pq.push({ 1,1,a[1][1] });
        while (!pq.empty()) {
            abc now = pq.top();
            pq.pop();
            if (now.c != d[now.x][now.y]) continue;
            for (int i = 0; i < 4; i++) {
                int nx=now.x+dx[i], ny=now.y+dy[i];
                if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
                if (d[nx][ny] > d[now.x][now.y] + a[nx][ny]) {
                    d[nx][ny] = d[now.x][now.y] + a[nx][ny];
                    pq.push({ nx,ny,d[nx][ny] });
                }
            }
        }
        printf("Problem %d: %d\n", ++t, d[n][n]);
    }
    return 0;
}