### Path sum: four ways题号：83 难度： 25 中英对照

NOTE: This problem is a significantly more challenging version of Problem 81.

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.

$$\begin{pmatrix} \color{red}{131} & 673 & \color{red}{234} & \color{red}{103} & \color{red}{18}\\ \color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & \color{red}{150}\\ 630 & 803 & 746 & \color{red}{422} & \color{red}{111}\\ 537 & 699 & 497 & \color{red}{121} & 956\\ 805 & 732 & 524 & \color{red}{37} & \color{red}{331} \end{pmatrix}$$

### Code

import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.PriorityQueue;

public final class p83 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

static public final int N=80;
static int map[][]=new int[N][N];
static int dis[]=new int[N*N+100];
static int cnt=0;
static boolean vis[]=new boolean[N*N+100];
static public class Edge implements Comparable<Edge>{
int to,cost;
public Edge(int to,int cost){this.to=to;this.cost=cost;}
public Edge(){this(0,1000000000);}
public int compareTo(Edge o) {
return Integer.compare(cost,o.cost);
}
}
static Edge edge[][]=new Edge[N*N][4];

static public String run(){
String fileName="p083_matrix.txt";
String line;
int index=0;
String[] ss=line.split(",");
for(int j=0;j<ss.length;j++)
map[index][j]=Integer.parseInt(ss[j]);
index++;
}
}catch(IOException e){
e.printStackTrace();
return null;
}
return dijkstra();
}
static public void addEdge(int x,int y,int i,int j){
//连边
if(i<0||i>=N||j<0||j>=N){
edge[x*N+y][cnt++]=new Edge();
}else
edge[x*N+y][cnt++]=new Edge(i*N+j,map[i][j]);
}
static public String dijkstra(){
//建图
for(int i=0;i<N;i++) for(int j=0;j<N;j++){
cnt=0;
}
//dijkstra
PriorityQueue<Edge> Q=new PriorityQueue<Edge>();
for(int i=0;i<N*N;i++) dis[i]=1000000000;
dis[0]=map[0][0];
while(!Q.isEmpty()){
Edge x=Q.poll();
int u=x.to;
if(vis[u]) continue;
vis[u]=true;
for(int i=0;i<4;i++){
if(dis[edge[u][i].to]>dis[u]+edge[u][i].cost){
dis[edge[u][i].to]=dis[u]+edge[u][i].cost;

425185