找到最大增益的最短路径

Question

Problem link我该如何修改我的代码，以便给我最大重量的最短路径。

问题概述：我给出一个矩阵，我必须从一个索引转到另一个索引最小的索引，每个索引都有一些增益，所以我必须找到最短路径（如果有多条最短路径可能，那么路径最大增益） 我的代码：

public static int min(int x , int y ,int endx,int endy,int n ,int m,int[][] p){ 
    int[] dirx ={1,-1,0,0 }; 
     int[] diry={0,0,1,-1}; 
     LinkedList<Point> som = new LinkedList<Point>(); 
     som.add(new Point(x,y)); 
     //dp[x][y]=p[x][y]; 

     while(!som.isEmpty()){ 
      Point xx = som.pop(); 
      for(int i=0;i<4;i++){ 

       int x1 = xx.x + dirx[i]; 
       int y1 = xx.y + diry[i]; 

       if(x1>=0 && x1<n && y1>=0 && y1<m && p[x1][y1]!=-1 && dp[x1][y1]==-1){ 

        dp[x1][y1] = dp[xx.x][xx.y]+ 1; 
        som.add(new Point(x1,y1)); 

       } 
      } 

     } 

    return dp[endx][endy]; 
} 

Answer 1

从您的代码添加

((dp[x1][y1]==-1) || ((dp[x1][y1] == dp[xx.x][xx.y] + 1) && (w[xx.x][xx.y]+p[x1][y1] > w[x1][y1]))) 

，而不是

(dp[x1][y1]==-1) 

和条件

w[x1][y1] = w[xx.x][xx.y] + p[x1][y1]; 

这意味着，如果你发现了同样的长度

你也可以优化不添加相同点几次的更好的方法，你会更新路径的结果，但我认为这里面在这个特定的问题中没有必要

Answer 2

这个问题可以用Dijkstra算法来解决。但是我们需要在原始算法中比较距离和增益量，而不仅仅是距离。

这些是我的一些代码提示，所以你只需要改变你的代码的一部分。

class Entry implements Comparable<Entry>{ 
    int x,y, dist, gain; 
    //Constructor is omitted. 
    public int compareTo(Entry o){ 
     if(dist != o.dist)//Compare distance first 
      return dist - o.dist; 
     return o.gain - gain;//Compare gain value 
    } 
} 

//Method signature is omitted 
PriorityQueue<Entry> q = new PriorityQueue(); 
q.add(new Entry(0,0,0,gain[0][0]); 
int[][][]dist = new int[n][m][2];//Assume size of matrix is n x m 
//Init dist array omitted 
dist[0][0][0] = 0;//Init distance 
dist[0][0][1] = gain[0][0];//Init gain amount, assume we have a gain matrix 
while(!q.isEmpty()){ 
    Entry e = q.poll(); 
    if(dist[e.x][e.y][0] == e.dist && dist[e.x][e.y][1] == e.gain){ 
     for(all valid next positions (a,b)) 
      if(dist[a][b][0] > e.dist + 1 || (dist[a][b][0] == e.dist + 1 && dist[a][b][1] < e.gain + gain[a][b]){ 
       //Notice the condition to update the dist array 
       dist[a][b][0] = e.dist + 1; 
       dist[a][b][1] = e.gain + gain[a][b]; 
       q.add(new Entry(a,b,e.dist + 1, e.gain + gain[a][b]); 
      } 
    } 
} 
return dist[n-1][m-1][1];