Tuesday, August 30, 2016
UVa 116 Unidirectional TSP
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(" %d ",min);
}
return 0;
}
Go to link download
