当前位置:首页 » Project Euler » 详细页

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} $$

Solution

将每个格子认为是一个节点,对所有节点将其与其附近一步可达的所有节点连边,边长(cost)等于目标节点的值。 然后该题变为一个$8\times 8$个节点、不超过$8\times 8 \times 3$条边的带权无向图。 最后利用迪杰斯特拉算法求其左上角到右下角的最短路,具体算法思路如下: 1. 将所有点的最短路径(用一个dis数组)先置为inf(一般取一个较大值即可,例如1000000000)。 2. 将起点可行走的边放入一个优先队列。 3. 每次从优先队列中取得cost最小的一个边,如果它的对面那个节点u我们没去过,那么走过去。 4. 走到目标点u后判断从该点出发的所有边,对于每个边,需要判断从u到它的目标点tp这条路径的距离是否比目标点to原本记录的最短路径短,如果短,则需要更新点to的最短路径值,并且把这条边作为可行边加入到优先队列中。 5. 依次循环上述内容,直至所有点都走过(优先队列为空)。 6. 右下角点对应的最短路径值即为答案。

Code

import java.io.BufferedReader;
import java.io.FileReader;
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";
		try(FileReader fr=new FileReader(fileName);
				BufferedReader in = new BufferedReader(fr);){
			String line;
			int index=0;
			while((line=in.readLine())!=null){
				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;
			addEdge(i,j,i,j+1);
		//	addEdge(i,j,i,j-1);
			addEdge(i,j,i+1,j);
			addEdge(i,j,i-1,j);
		}
		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];
		Q.add(new Edge(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;
					Q.add(new Edge(edge[u][i].to,dis[edge[u][i].to]));
				}
			}
		}
		int ans=1000000000;
		for(int i=0;i<N;i++)
			ans=Math.min(ans,dis[i*N+(N-1)]);
		return ans;
	}
}
260324
168ms