### Path sum: three ways题号：82 难度： 20 中英对照

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

The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994.

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

### Code

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

public final class p82 {
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][3];

static public String run(){
String fileName="p082_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;
}
//建图
for(int i=0;i<N;i++) for(int j=0;j<N;j++){
cnt=0;
}
int ans=1000000000;
for(int i=0;i<N;i++)
ans=Math.min(ans,dijkstra(i));
return Integer.toString(ans);
}
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 int dijkstra(int s){
//Dijkstra
PriorityQueue<Edge> Q=new PriorityQueue<Edge>();
for(int i=0;i<N*N;i++){
dis[i]=1000000000;
vis[i]=false;
}
dis[s*N+0]=map[s][0];
while(!Q.isEmpty()){
Edge x=Q.poll();
int u=x.to;
if(vis[u]) continue;
vis[u]=true;
for(int i=0;i<3;i++){
if(dis[edge[u][i].to]>dis[u]+edge[u][i].cost){
dis[edge[u][i].to]=dis[u]+edge[u][i].cost;

260324