[UVa] 116 - Unidirectional TSP

#include <stdio.h>

int dir[100][100];
int mtx[100][100];
int path[100];

int main()
{
 int a, b, c, min;
 int i, j, row, col, a_dir, c_dir;

 while (scanf("%d %d",&row,&col)==2)
 {
     for (i=1 ; i<=row ; i++)
            for (j=1 ; j<=col ; j++)
                scanf("%d",&mtx[i][j]);

        for (j=col-1 ; j>=1 ; j--)
        {
            for (i=1 ; i<=row ; i++)
            {
                if (i-1<1)
                {
                    a_dir = -1;
                    a = mtx[i][j] + mtx[row][j+1];
                } else
                {
                    a_dir = 0;
                    a = mtx[i][j] + mtx[i-1][j+1];
                }
                if (i+1>row)
                {
                    c_dir = -1;
                    c = mtx[i][j] + mtx[1][j+1];
                } else
                {
                    c_dir = 0;
                    c = mtx[i][j] + mtx[i+1][j+1];
                }
                b = mtx[i][j] + mtx[i][j+1];

                if (a<=b && a<=c)
                {
                    mtx[i][j] = a;

                    if (a_dir<0)
                    {
                        if (a==b) { dir[i][j] = i; }
                        else if (a==c) { dir[i][j] = i+1; }
                        else { dir[i][j] = row; }
                    } else {
                        if (a==c && c_dir<0) dir[i][j] = 1;
                        else dir[i][j] = i-1;
                    }
                }
                else if (b<=a && b<=c)
                {
                    mtx[i][j] = b;


                    if (b==a)
                    {
                        if (a_dir<0)
                        {
                            dir[i][j] = i;
                        } else
                        {
                            dir[i][j] = i-1;
                        }
                    } else if (b==c)
                    {
                        if (c_dir<0)
                        {
                            dir[i][j]=1;
                        } else
                        {
                            dir[i][j]=i;
                        }
                    } else
                    {
                        dir[i][j] = i;
                    }

                }
                else if (c<=a && c<=b)
                {
                    mtx[i][j] = c;
                    if (c_dir<0)
                    {
                        dir[i][j] = 1;
                    } else {
                        if (c==a) { dir[i][j]=i-1; }
                        else if (c==b) { dir[i][j]=i; }
                        else { dir[i][j]=i+1; }
                    }
                }

            }
        }

        for (i=1, min=mtx[1][1], path[1]=1 ; i<=row ; i++)
        {
            if (mtx[i][1]<min)
            {
                min = mtx[i][1];
                path[1] = i;
            }
        }
        printf("%d",path[1]);
        for (j=2 ; j<=col ; j++)
        {
            path[j] = dir[path[j-1]][j-1];
            printf(" %d",path[j]);
        }


        printf("\n%d\n",min);

 }

 return 0;
}