116 - Unidirectional TSP - UVA

dynamic programming

All you have to do is to find a path that have the minimal weight path.

I first started to construct my table from the first column and in each step I picked the minimum weight till that step that had the minimum row, but that was wrong because if there are several paths, my program might pick the wrong path.

for example ( nimA, one of my friends pointed this test case out )

4 3

2 1 1

2 1 2

1 2 2

1 2 2

my program produced

4 1 1

3

but the correct answer is

3 2 1

3

that is lexicographically smaller.

I first construct the last column of my table

dp[i][n] = a[i][n] for all i

then I want to construct the rest of my table, in each cell [i][j] I can go to next column one row upper, same row, or one row lower, I pick the minimum value of them and when I have several minimum I pick the one with minimum row.

for( int j = n-1; j >= 1; j --)

for(int i = 1; i <= m; i ++)

in these two loops I fill my table and finally I find my minimum in the first column and print the path.