http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=52 my Accepted solution to "Unidirectional TSP"

makefile

CFLAGS=-ansi -g
OUT=uniTSP
SRC=uniTSP.c
CC=gcc
RM=rm

$(OUT): $(SRC)
	$(CC) $(SRC) $(CFLAGS) -o $(OUT)

clean:
	$(RM) -f $(OUT)

test: $(OUT)
	./$(OUT) < testData

testData

5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 1 2 3
2 2
9 10 9 10

uniTSP.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>

#define NDEBUG /* uncomment to remove debugging statements */
#define MAX_ROWS 10
#define MAX_COLS 100

const int NO_SOLUTION = INT_MAX;

struct rowColWeightTriple {
   int row;
   int col;
   int weight;
};

int pathWeight(
   const int cr, const int cc, 
   const int R, const int C,
   const int M[MAX_ROWS][MAX_COLS], 
   int SM[MAX_ROWS][MAX_COLS]);

int compareRowColWeight( const void * first, const void * second );

void printGreedyWalk( 
   const int cr,
   const int cc, 
   const int R, 
   const int C, 
   const int SM[MAX_ROWS][MAX_COLS]);

int isDebugging();

int main() {
   int userR;
   int userC;
   int userM[MAX_ROWS][MAX_COLS];
   int solutionM[MAX_ROWS][MAX_COLS];

   while( scanf("%i %i", &userR, &userC) == 2 ) {
      assert( userR <= MAX_ROWS );
      assert( userC <= MAX_COLS );

      int i, j;

      /* initialization matrix */
      for( i = 0; i < userR; ++i ) {
         for( j = 0; j < userC; ++j ) {

            /* initialize solution matrix to empty */
            solutionM[i][j] = NO_SOLUTION;

            /* read an integer into the current position of userM */
            int intsRead = scanf("%i", &userM[i][j]);

            /* ensure that the read completed */
            assert(intsRead == 1);
         }
      }

      /* compute optimal path for each leftmost node 
       * note that this is the same as computing the entire solution matrix
       * this loop also instantiates stringRow, which keeps track
       * of the weight of each path starting from the left as well as 
       * the starting row index. */
      struct rowColWeightTriple startingRow[userR];

      for( i = 0; i < userR; ++ i ) {
         startingRow[i].col = 0;
         startingRow[i].row = i;
         startingRow[i].weight = 
            pathWeight(i, 0, userR, userC,
               userM,
               solutionM);
      }

      /* sort ordered triples by weight, then by row index */
      qsort(
         startingRow, 
         userR, 
         sizeof(struct rowColWeightTriple), 
         compareRowColWeight);

      /* if debugging, print out solution matrix */
      if( isDebugging() ) {
         printf("solution matrix:\n");
         for( i = 0; i < userR; ++ i ) {
            for( j = 0; j < userC; ++ j ) {
               printf("%-4i", solutionM[i][j]);
            }

            printf("\n");
         }

         printf("\nsorted row/weight pairs:\n");
         for( i = 0; i < userR; ++ i ) {
            printf("(%i, %i)\n", 
               startingRow[i].row,
               startingRow[i].weight);
         }
         printf("\n");
      }

      /* print greedy walk through solution matrix,
       * starting from position with known shortest
       * path. */
      printGreedyWalk( 
         startingRow[0].row,
         0, 
         userR,
         userC, 
         (const int * const * const) solutionM);

      printf( "\n%i\n", startingRow[0].weight );
   }

   return 0;
}

/*
 * cr - current row
 * cc - current column
 * R - number of rows
 * C - number of columns
 * M - weight matrix
 * SM - solution matrix
 */
int pathWeight(
   const int cr, const int cc, 
   const int R, const int C,
   const M[MAX_ROWS][MAX_COLS],
   int SM[MAX_ROWS][MAX_COLS]) {

   assert( 0 <= cr && cr < R);
   assert( 0 <= cc && cc < C);

   int i, j;

   /* have we solved this subproblem yet?
    * if so, just return the result */
   if(SM[cr][cc] != NO_SOLUTION) {

      return SM[cr][cc];
   }

   /* base case, we've moved accross and hit the last column */
   if( cc == C - 1 ) {

      /* retrieve weight from weight matrix */
      int thisWeight = M[cr][C-1];

      /* store this weight in the solution matrix */
      SM[cr][C-1] = thisWeight;

      return thisWeight;

   /* otherwise we're on a column with neighbors to the right */   
   } else {
      /* instantiate three ordered triples, one per neighbor */
      struct rowColWeightTriple neighbors[3];

      /* compute row/col values of right neighbors */
      neighbors[0].row = (cr - 1 + R) % R;
      neighbors[0].col = cc + 1;

      neighbors[1].row = cr;
      neighbors[1].col = cc + 1;

      neighbors[2].row = (cr + 1 + R) % R;
      neighbors[2].col = cc + 1;

      /* loop over neighbors and compute path weights */
      for(  i = 0; i < 3; ++i ) {
         neighbors[i].weight = pathWeight(
            neighbors[i].row,
            neighbors[i].col,
            R, C, M, SM);

         /* memoize */
         SM[ neighbors[i].row ] [ neighbors[i].col ] 
            = neighbors[i]. weight;
      }

      /* sort ordered triples by weight, then by row index */
      qsort(
         neighbors, 
         3, 
         sizeof(struct rowColWeightTriple), 
         compareRowColWeight);

      /* if debugging, print neighbors */
      if( isDebugging() ) {
         printf("for node at (%i, %i), sorted neighbor triples: \n", cr, cc);
         for( i = 0; i < 3; ++i ) {
            printf("(%i, %i, %i)\n", 
               neighbors[i].row, neighbors[i].col, neighbors[i].weight);
         }
         printf("\n");
      }
 
      /* get pointer to first item in sorted list */
      const struct rowColWeightTriple * bestN = &neighbors[0];

      /* memoize */
      SM[cr][cc] = M[cr][cc] + bestN -> weight;
  
      /* we now have the index of the best immediate neighbor, 
       * sum the values and return the result */
      return M[cr][cc] + bestN -> weight;
   }
}

int compareRowColWeight( const void * first, const void * second ) {
   const struct rowColWeightTriple
      * firstTriple = (struct rowColWeightTriple *) first, 
      * secondTriple = (struct rowColWeightTriple *) second;

   const int weightDifference = 
      firstTriple -> weight - secondTriple -> weight;

   /* if weights are the same... */
   if( weightDifference == 0 ) {
      /* return the difference in rows */
      return firstTriple -> row - secondTriple -> row;
   } else {
      /* otherwise return the difference in weights */
      return weightDifference;
   }
}

void printGreedyWalk( 
   const int cr,
   const int cc, 
   const int R, 
   const int C, 
   const int SM[MAX_ROWS][MAX_COLS] ) {

   int i, j;

   /* check base case */
   if( cc > C - 1 ) {
      return; 
   }

   /* print cr (account for index) */
   printf("%i", cr + 1);

   /* only print trailing space if we're not at the last column */
   if( cc != C - 1) {
      printf(" ");
   }

   /* compute row/col values of right neighbors */
   struct rowColWeightTriple neighbors[3];

   neighbors[0].row = (cr - 1 + R) % R;
   neighbors[0].col = cc + 1;

   neighbors[1].row = cr;
   neighbors[1].col = cc + 1;

   neighbors[2].row = (cr + 1 + R) % R;
   neighbors[2].col = cc + 1;

   /* just get weights from solution matrix */
   for( i = 0; i < 3; ++i ) {
      neighbors[i].weight = SM[ neighbors[i].row ] [ neighbors[i].col ];
   } 

   /* sort neighbors increasing */
   qsort(
      neighbors, 
      3, 
      sizeof(struct rowColWeightTriple), 
      compareRowColWeight);

   /* recurse */
   printGreedyWalk(
      neighbors[0].row,
      neighbors[0].col,
      R, C, SM);
}

int isDebugging() {
   #ifndef NDEBUG
   return 1;
   #else
   return 0;
   #endif
}