UVa 116 - Unidirectional TSP

// UVa 116 - Unidirectional TSP
// Dynamic Programming
// O(m*n)

#include <stdio.h>
#include <algorithm>
using namespace std;

const int maxm = 102;
const int maxn = 102;

typedef signed long long int ll;

ll A[maxm][maxn], T[maxm][maxn];
int R[maxm][maxn];

int main() {
	int n, m;
	while (scanf("%d%d", &m, &n) != EOF) {

		// input
		for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
				scanf("%lld", &A[i][j]);

		// base cases
		for (int i = 0; i < m; i++)
			T[i][n - 1] = A[i][n - 1];

		// DP
		for (int j = n - 2; j >= 0; j--)
			for (int i = 0; i < m; i++) {
				int up = i > 0 ? i - 1 : m - 1;
				int mid = i;
				int down = i < m - 1 ? i + 1 : 0;

				int a = min(up, min(mid, down));
				int c = max(up, max(mid, down));
				int b = up + mid + down - a - c;

				if (T[a][j + 1] <= T[b][j + 1] && T[a][j + 1] <= T[c][j + 1]) {
					R[i][j] = a;
					T[i][j] = T[a][j + 1] + A[i][j];
				} else if (T[b][j + 1] <= T[c][j + 1]) {
					R[i][j] = b;
					T[i][j] = T[b][j + 1] + A[i][j];
				} else {
					R[i][j] = c;
					T[i][j] = T[c][j + 1] + A[i][j];
				}
			}

		// select minimum solution
		int sol[maxn];
		sol[0] = 0;
		for (int i = 1; i < m; i++)
			if (T[i][0] < T[sol[0]][0])
				sol[0] = i;

		// output
		for (int j = 1; j < n; j++)
			sol[j] = R[sol[j - 1]][j - 1];
		for (int j = 0; j < n - 1; j++)
			printf("%d ", sol[j] + 1);
		printf("%d\n", sol[n - 1] + 1);
		printf("%lld\n", T[sol[0]][0]);

	}
	return 0;
}