import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main{
public static class Node implements Comparable<Node>{
int y,x,leng;
Node(int y, int x, int leng){
this.y = y;
this.x = x;
this.leng = leng;
}
@Override
public int compareTo(Node o) {
return this.leng-o.leng;
}
}
static int[][] cave,leng;
static boolean[][] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int count = 1;
while(true) {
int N = Integer.parseInt(br.readLine());
if(N==0) {
bw.flush();
bw.close();
br.close();
return;
}
//동굴,방문배열 생성
cave = new int[N][N];
visited = new boolean[N][N];
leng = new int[N][N];
for(int i=0; i<N; i++) {
Arrays.fill(leng[i], Integer.MAX_VALUE);
}
//동굴 정보 입력
for(int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++) {
cave[i][j] = Integer.parseInt(st.nextToken());
}
}
PriorityQueue<Node> queue = new PriorityQueue<Node>();
leng[0][0] = cave[0][0];
queue.add(new Node(0,0,leng[0][0]));
int[] move_y = {1,-1,0,0};
int[] move_x = {0,0,-1,1};
while(!queue.isEmpty()) {
Node curr = queue.poll();
if(visited[curr.y][curr.x]) continue;
visited[curr.y][curr.x] = true;
if(curr.y==N-1 && curr.x==N-1) {
bw.write("Problem "+count+": "+curr.leng+"\n");
count++;
break;
}
for(int i=0; i<4; i++) {
int new_y = curr.y+move_y[i];
int new_x = curr.x+move_x[i];
if(new_y<0 || new_y>=N || new_x<0 || new_x>=N || visited[new_y][new_x]) continue;
queue.add(new Node(new_y,new_x,curr.leng+cave[new_y][new_x]));
}
}
}
}
}
도착지점까지 갔을때 잃는 루피의 최소거리를 구해줘야 하므로 다익스트라 알고리즘을 사용하였다.
우선순위큐를 사용하여 시간을 줄여주었고 우선순위큐에서 컴퍼레이블을 사용하여 루피의 누적 수를 기준으로 poll을 하게 변경해주었다.