本文共 1258 字，大约阅读时间需要 4 分钟。

原题链接：
分类：TSP
备注：多段图的最短路；字典序最小解

#include<bits/stdc++.h>using namespace std;const int inf=0x3f3f3f3f;int m,n,a[15][105],d[15][105],nxt[15][105],first;int main(void){       // freopen("in.txt","r",stdin);    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;        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;                             nxt[i][j]=rows[k];                        }                    }                }                if(j==0&&d[i][j]<ans){                       ans=d[i][j]; first=i;                }            }        }        printf("%d",first+1);        for(int i=nxt[first][0],j=1;j<n;i=nxt[i][j],j++)            printf(" %d",i+1);        printf("\n%d\n",ans);    }    return 0;}