题目大意：
思路：dp逆推。
由最后一列推到第一列。记录路径（只要记录由下一列转化而来的行）。

#include <bits/stdc++.h>
using namespace std;

int a[105][105];
int dp[105][105];
int Next[105][105];
int main()
{
    int n, m;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        for(int i=1;i<=n;i++)
        {
            dp[i][m]=a[i][m];
        }
        for(int i=m-1;i>=1;i--)
        {
            for(int j=1;j<=n;j++)
            {
                dp[j][i]=(1<<31)-1;
                int x[3]={j-1, j, j+1};
                for(int k=0;k<=2;k++)//对路径的处理
                {
                    if(x[k]==0)
                    {
                        x[k]=n;
                    }
                    if(x[k]==n+1)
                    {
                        x[k]=1;
                    }
                }
                sort(x, x+3);
                for(int k=0;k<3;k++)
                {
                    if(dp[x[k]][i+1]<dp[j][i])
                    {
                        dp[j][i]=dp[x[k]][i+1];
                        Next[j][i]=x[k];
                    }
                }
                dp[j][i]+=a[j][i];
            }
        }
        int ans=(1<<31)-1, p;
        for(int i=1;i<=n;i++)
        {
            if(dp[i][1]<ans)
            {
                ans=dp[i][1];
                p=i;
            }
        }
        printf("%d%c",p,(m==1?'\n':' '));
        for(int i=1;i<m;i++)
        {
            printf("%d%c",Next[p][i],(i==m-1?'\n':' '));
            p=Next[p][i];
        }
        printf("%d\n",ans);
    }

	return 0;
}