UVa116 - Unidirectional TSP

dp[i, j] 表示在(i, j)这个点到最后一列和最小的路程，逆序求解的优点在于可以顺序打印路径。本题还要求得出字典序最小的序列，那么在每次状态转移时优先考虑字典序最小的数即可

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 110, INF = 2e9;

int m, n;
int g[N][N];
int nexti[N][N];
int dp[N][N];

int main() {
  while (scanf("%d%d", &m, &n) != EOF) {
    for (int i = 1; i <= m; i++)
      for (int j = 1; j <= n; j++) scanf("%d", &g[i][j]);

    int ans = INF, first = 0;
    for (int j = n; j >= 1; j--)
      for (int i = 1; i <= m; i++) {
        if (j == n)
          dp[i][j] = g[i][j]; // 初始化为最后一列的数
        else {
          int row[3] = {i, i - 1, i + 1};
          if (i == 1) row[1] = m;
          if (i == m) row[2] = 1;
          sort(row, row + 3); // 保证字典序最小
          dp[i][j] = INF;
          for (int k = 0; k < 3; k++) {
            int v = dp[row[k]][j + 1] + g[i][j];
            if (v < dp[i][j]) {
              dp[i][j] = v;
              nexti[i][j] = row[k]; // 更新父节点
            }
          }
        }
        if (j == 1 && dp[i][j] < ans) {
          ans = dp[i][j];
          first = i;
        }
      }
    printf("%d", first);
    for (int i = nexti[first][1], j = 2; j <= n; i = nexti[i][j], j++)
      printf(" %d", i);
    printf("\n%d\n", ans);
  }
  return 0;
}