多段图的最短路问题 。  运用了非常多的技巧 ：如 记录字典序最小路径 。

细节參见代码：

#include<bits/stdc++.h>

using namespace std;

const int INF = 2000000000;

int m,n,a[15][105],d[15][105],next_[15][105];

int main() {

    while(~scanf("%d%d",&m,&n)) {

        for(int i=0;i<m;i++)

            for(int j=0;j<n;j++) scanf("%d",&a[i][j]);

        int ans = INF,first = 0;

        for(int j=n-1;j>=0;j--) {

            for(int i=0;i<m;i++) {

                if(j == n-1) d[i][j] = a[i][j]; //边界

                else {

                    int rows[3] = {i,i-1,i+1};

                    if(i==0) rows[1] = m-1;

                    if(i==m-1) rows[2] = 0;

                    sort(rows,rows+3);    //又一次排序，以便找到字典序最小的

                    d[i][j] = INF;

                    for(int k=0;k<3;k++) {

                        int v = d[rows[k]][j+1] + a[i][j];

                        if(v < d[i][j]) { d[i][j] = v; next_[i][j] = rows[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<n;i=next_[i][j],j++) printf(" %d",i+1);

        printf("\n%d\n",ans);

    }

    return 0;

}