[Baekjoon] #4485 녹색 옷 입은 애가 젤다지?

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

class Location{
	int x;
	int y;
	int w;
	
	public Location(int x, int y, int w) {
		// TODO Auto-generated constructor stub
		this.x = x;
		this.y = y;
		this.w = w;
	}
}

public class Main {
	
	static int n;
	static int[][] map;
	static int[][] dist;
	static PriorityQueue<Location> q;
	static int[][] visit;
	static int cnt = 0;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
	
		while(true){
			
			n = sc.nextInt();
			if(n==0){
				return;
			}
			cnt++;
			map = new int[n][n];
			dist = new int[n][n];
			q = new PriorityQueue<>(new Comparator<Location>() {
				public int compare(Location l1, Location l2){
					return Integer.compare(l1.w, l2.w);
				}
			});
			visit = new int[n][n];
			
			
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++){
					map[i][j] = sc.nextInt();
					dist[i][j] = 999999;
				}
			}
			
			visit[0][0] = 1;
			dist[0][0] = map[0][0];
			q.offer(new Location(0, 0, map[0][0]));
			getDijkstra();
			System.out.println("Problem "+cnt+": "+dist[n-1][n-1]);
		}
	}
	
	public static void getDijkstra(){
		
		int[] xx = {-1,0,1,0};
		int[] yy = {0,1,0,-1};
		
		while(!q.isEmpty()){
			
			int x = q.peek().x;
			int y = q.poll().y;
			
			for(int i=0;i<4;i++){
				
				int ax = x+xx[i];
				int ay = y+yy[i];
				
				if(ax>=0 && ay>=0 && ax<n && ay<n){
					if(dist[ax][ay] > dist[x][y] + map[ax][ay]){
						dist[ax][ay] = dist[x][y] + map[ax][ay];
						q.offer(new Location(ax, ay, map[ax][ay]));
					}
				}
				
			}
			
		}
	}
}