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;
}

沒有留言:

張貼留言