2013年1月10日

UVa 116 - Unidirectional TSP

```#include <stdio.h>

int small(int a, int b) {
return a < b ? a : b;
}

int big(int a, int b) {
return a > b ? a : b;
}

int main() {
int R, C, r, c;
while (scanf("%d%d", &R, &C) == 2) {
int num[101][101] = {}, dp[101][101] = {}, next[101][101] = {};
for (r = 0; r < R; r++)
for (c = 0; c < C; c++)
scanf("%d", &num[r][c]);
for (c = C - 1; c >= 0; c--)
for (r = 0; r < R; r++) {
int r1 = (r - 1 + R) % R, r2 = r, r3 = (r + 1) % R;
int up = small(r1, small(r2, r3)), down = big(r1, big(r2, r3)), mid = r1 + r2 + r3 - up - down;
int min = dp[up][c + 1];
next[r][c] = up;
if (dp[mid][c + 1] < min) min = dp[mid][c + 1], next[r][c] = mid;
if (dp[down][c + 1] < min) min = dp[down][c + 1], next[r][c] = down;
dp[r][c] = num[r][c] + min;
}
int dis = 2e9, ans, c = 0;
for (r = 0; r < R; r++)
if (dp[r][0] < dis) dis = dp[r][0], ans = r;
while (c < C) {
printf("%d%s", ans + 1, c == C - 1 ? "\n" : " ");
ans = next[ans][c++];
}
printf("%d\n", dis);
}
return 0;
}
```