这道题在递推方式和那个数字三角形有一点相像，很容易推出来
但是这道题要求的是字典序，这里就有一个递推顺序的问题
这里用逆推，顺推会很麻烦，为什么呢？
如果顺推的话，最后一行假设有种情况是最小值，那么你怎么知道哪一种的
是字典序最小？最后一行的数字最小显然不一定整个路径的字典序最小，因为
字典序是从第一行开始比较的。
如果非要这么做的话可以把这几种情况的路径全部记下来，
然后排序，选出最小的输出。同时输出路径还要写一个递归。这样显然很麻烦。
但是如果是逆推的话，我们推到最后是第一行，这个时候如果有多种情况是
最小值，显然第一行最小肯定字典序最小，这个时候就可以选出答案，直接
输出就可以了。
所以以后这种要求字典序的题要考虑逆推
#include<cstdio>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 112;
int a[MAXN][MAXN], d[MAXN][MAXN], Next[MAXN][MAXN];
int n, m;int main()
{while(~scanf("%d%d", &n, &m)){REP(i, 0, n)REP(j, 0, m)scanf("%d", &a[i][j]);int ans = 1e9, first = 0;for(int j = m - 1; j >= 0; j--)REP(i, 0, n){if(j == m - 1) d[i][j] = a[i][j];else{int row[3] = {i, (i - 1 + n) % n, (i + 1) % n};d[i][j] = 1e9;sort(row, row + 3);REP(k, 0, 3){int v = a[i][j] + d[row[k]][j+1];if(v < d[i][j]) { d[i][j] = v; Next[i][j] = row[k]; }}}if(j == 0 && d[i][j] < ans) { ans = d[i][j]; first = i; }}printf("%d", first + 1);for(int i = Next[first][0], j = 1; j < m; i = Next[i][j], j++)printf(" %d", i + 1);printf("\n%d\n", ans);}return 0;
}