Can someone please help explain how the graph would be represented in order to run LIS on it to find the shortest path?

My thought is to assume an adjacency matrix size NxN and run a shortest path on this somehow using LIS. I'm not sure if this is the right track or not.

Thanks in advance for any help!

Practice problem:

Given an undirected graph G having N (1<N><=1000) vertices and positive weights. Find the shortest path from vertex 1 to vertex N, or state that such path doesnÃ¢ÂÂt exist.

Hint: At each step, among the vertices which werenÃ¢ÂÂt yet checked and for which a path from vertex 1 was found, take the one which has the shortest path, from vertex 1 to it, yet found.]]>

I am not sure I exactly understand the problem.

Does the sequence has to be consecutive?

Or the goal is to find the maximum number of numbers appearing after each other in a non-decreasing manner with or without any other number between them?

Thanks]]>

Actually, I also cannot really understand how the value can become 5.

Besides what was mentioned above by ol0rin, tutorial also says to increase by one: "we make S[i]=S[j]+1"

Please, anyone clarify more why it is 5.

Thanks.]]>

The approach used for a single run, tries to take a path which will maximize the total stars. But here we have the ability to run three runs. So the approach has to be cover the maximum possible number of cells using the three paths. Consider this test case, and watch the above solution fail : "0 9 8 3 4 3 4", "2 3 4 2 4 2 3", "2 3 4 2 3 4 2".

To do that the solution is pretty tough. That's why this problem is listed under Advanced category in the DP tutorial.

The breakthrough is to realize that there are three paths going from upper left corner, to lower right corner. And they all need to go through all the rows at some point of the time.

So let us have an array[50][50][50], where array[i][j][k] will depict the left path to be in column i, middle in column j, and right in column k.

Another thing is the paths must not intersect in rows 1 till n-2. They can overlap in row 0 and row n-1. (Use a few examples to convince yourself.)

So we begin our journey from Row 0.

array[i][j][k] where i < j < k, will be equal to sum (level[0][i]) 0<=i <= k.

Now comes the route from Row1 to row n-2,

array1[i][j][k] where i<j><k = array[i][j][k] + level[1][i] + level[1][j] + level[1][k].

This depicts the movement in vertical direction of all the three paths.

But the paths may move towards right in a given row as well.

To manage that also, we need to consider 8 scenarios,

where left moves from left-1 to left, but middle, and right come vertically down.

That would be array1[i][j][k] = array1[i-1][j][k] + level[1][i];

other 7 cases are like, (i,m-1,r) -----> (i,m,r), (i-1,m-1,r) -----> (i,m,r) ....Hope you are getting it.]]>

]]>

/**

* Find the shortest path from vertex 0 to vertex N-1 or state that such a path

doesn't exist where the graph is represented by the adjacency matrix

* dist[i][j], and the cost of passing through vertex i is cost[i] and

* the money available for the trip is M.

* @param M

* @param dist

* @param cost

* @return

*/

public int shortestPath(int M, int[][] dist, int[] cost) {

int n = cost.length;

int mSize = M + 1;

//Set states(i,j) as unvisited for all (i,j)

boolean[][] visited = new boolean[n][];

for (int i = 0; i < n; i++) {

visited[i] = new boolean[n];

}

//Set memo[i][j] to Infinity for all (i,j)

int[][] memo = new int[n][mSize];

for (int i = 0; i < n; i++) {

memo[i] = new int[mSize];

Arrays.fill(memo[i], Integer.MAX_VALUE);

}

memo[0][M] = 0;

int lastK = -1;

int lastL = -1;

while (true) {

// Among all unvisited states(i,j) find the one for which memo[i][j]

// is the smallest. Let this state found be (k,l).

int k = -1;

int l = -1;

int min = Integer.MAX_VALUE;

for (int i = 0; i < memo.length; i++) {

for (int j = 0; j < memo[0].length; j++) {

if (visited[i][j]) {

continue;

}

if (memo[i][j] < min) {

k = i;

l = j;

min = memo[i][j];

}

}

}

if (k == -1) {

break;

}

if ((k == lastK) && (l == lastL)) {

break;

}

lastK = k;

lastL = l;

for (int p = 0; p < n; p++) {

// neighbors have dist < inf

if (dist[k][p] == Integer.MAX_VALUE) {

continue;

}

if (visited[k][p]) {

continue;

}

visited[k][p] = true;

int c0 = l - cost[p];

//If (l-S[p]>=0 AND

// memo[p][l-S[p]]>memo[k][l]+Dist[k][p])

// Then memo[p][l-S[p]]=memo[k][l]+Dist[k][p]

if ((c0 >= 0) &&

((memo[p][c0] == Integer.MAX_VALUE) ||

(memo[p][c0] > (memo[k][l] + dist[k][p])))) {

memo[p][c0] = (memo[k][l] + dist[k][p]);

}

}

}

//Find the smallest number among memo[N-1][j] (for all j, 0<=j<=M);

//if there are more than one such states, then take the one with greater

//j. If there are no states(N-1,j) with value less than Infinity - then

//such a path doesn't exist.

int min = Integer.MAX_VALUE;

for (int j = M; j > -1; j--) {

if (memo[n - 1][j] < min) {

min = memo[n - 1][j];

}

}

// shortest path (which is the sum of the distances) for which total cost < M

return min;

}

using namespace std;

int main()

{

// here are the changes

int i,j,sum,coins[]={1,3,5};

cin>>sum;

int min[sum+1];

// end of changes

for(i=0;i<=sum;i++)

min[i]=99;

min[0]=0;

for(i=1;i<=sum;i++)

{

for(j=0;j<3;j++)

{

if( ( coins[j]<=i) && (min[ i - coins [ j ] ] + 1 < min[i] ) )

{

min[i]=min[i-coins[j]] +1;

// cout<<endl;

}

//cout><<"im out of if condition";

}

}

cout<<min[sum];

return 0;

}>]]>

Can someone explain the logic behind the solution of this Jewelry problem?]]>