dfs求有权最短路

import java.util.*;
public class Main{
    static int n,N=1000,INF=0x3f3f3f3f;
    static int g[][]=new int[N][N];
    static int d[][]=new int[N][N];
    static int bfs(){
        Queue<Pair> q=new LinkedList<>();
        q.offer(new Pair(0,0));
        d[0][0]=g[0][0];
        int dx[]={0,1};
        int dy[]={1,0};
        while(!q.isEmpty()){
            Pair t=q.poll();
            for(int i=0;i<2;i++){
                int x=t.a+dx[i];
                int y=t.b+dy[i];
                if(x>=0&&x<n&&y>=0&&y<n&&g[x][y]!=-1){
                    q.offer(new Pair(x,y));
                    d[x][y]=Math.min(d[x][y],d[t.a][t.b]+g[x][y]);
                }
            }
        }
        return d[n-1][n-1];
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                d[i][j]=INF;
                g[i][j]=sc.nextInt();
            }
        }
        int t=bfs();
        System.out.println(t==INF?"Sorry":t);
    }
   static class Pair{
        int a=0;int b=0;
       public Pair(int x,int y){
            a=x;b=y;
        }
    }
}