BOJ 4485

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

#define MAXN 125

int N;
int map[MAXN][MAXN];
int dist[MAXN][MAXN];
struct node{
    int x,y,cost;
    bool operator < (const node& a) const{
        return a.cost < cost;
    }
};
int dx[] = {0,0,1,-1};
int dy[]= {1,-1,0,0};

priority_queue<node> pq;
int dijkstra(){
    pq.push({0,0,map[0][0]});
    dist[0][0] = map[0][0];
    while (!pq.empty()){
        int x = pq.top().x;
        int y = pq.top().y;
        int cur_cost = pq.top().cost;
        pq.pop();
        if (cur_cost != dist[x][y]) continue;
        for (int i = 0 ;i < 4; i++){
            int nx = x +dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0|| nx>=N || ny>=N) continue;
            int next_cost = cur_cost + map[nx][ny];
            if (dist[nx][ny] == -1 || (dist[nx][ny]!= -1 && dist[nx][ny]> next_cost)){
                dist[nx][ny] = next_cost;
                pq.push({nx,ny,next_cost});
            }
        }
    }
    return dist[N-1][N-1];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 0;
    while (1){
        t++;
        cin >> N;
        if (N ==0) break;
        memset(dist,-1,sizeof(dist));
        for (int i =0 ;i<N; i++){
            for (int j= 0;j<N;j++){
                cin >> map[i][j];
            }
        }
        printf("Problem %d: %d\n",t,dijkstra());
    }
    return 0;
}