Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

Unidirectional TSP

116.c

#include <stdio.h>
#include <stdlib.h>

int tablero[100][100];
int dist[100][100];
int dir[100][100];
int m, n;

void
calc(void)
{
	int i,j;
	int min;
	int a;

	for(j=0; j<m; j++) {
		dist[j][n-1]=tablero[j][n-1];
	}

	for(i=n-2; i>=0; i--) {
		dist[0][i] = dist[0][i+1];
		dir[0][i] = 0;
		if (m>1) if (dist[1][i+1] < dist[0][i]) {
			dist[0][i] = dist[1][i+1];
			dir[0][i] = 1;
		}
		if (m>1) if (dist[m-1][i+1] < dist[0][i]) {
			dist[0][i] = dist[m-1][i+1];
			dir[0][i] = -1;
		}
		dist[0][i] += tablero[0][i];
		for(j=1; j<m-1; j++) {
			dist[j][i] = dist[j-1][i+1];
			dir[j][i] = -1;
			if (dist[j][i+1] < dist[j][i]) {
				dist[j][i] = dist[j][i+1];
				dir[j][i] = 0;
			}
			if (dist[(j+1)%m][i+1] < dist[j][i]) {
				dist[j][i] = dist[(j+1)%m][i+1];
				dir[j][i] = 1;
			}
			dist[j][i] += tablero[j][i];
		}
		dist[j][i] = dist[0][i+1];
		dir[j][i] = 1;
		if (dist[j-1][i+1] < dist[j][i]) {
			dist[j][i] = dist[j-1][i+1];
			dir[j][i] = -1;
		}
		if (dist[j][i+1] < dist[j][i]) {
			dist[j][i] = dist[j][i+1];
			dir[j][i] = 0;
		}
		dist[j][i] += tablero[j][i];
	}
	min=0;
	for(i=0; i<m; i++) {
		if (dist[i][0] < dist[min][0]) {
			min=i;
		}
	}
	printf("%d", min+1);
	a=min;
	for(i=1; i<n; i++) {
		a = (a+dir[a][i-1]+m)%m;
		printf(" %d", a+1);
	}
	printf("\n%d\n", dist[min][0]);
}

int
main(void)
{
	int i,j;

	while(1) {
		if (scanf("%d %d", &m, &n)!=2) {
			break;
		}
		if (m<1 || m>10 || n<1 || n>100) {
			abort();
		}
		for(i=0; i<m; i++) {
			for(j=0; j<n; j++) {
				if (scanf("%d", &tablero[i][j]) != 1) {
					abort();
				}
			}
		}
		calc();
	}
	exit(0);
}