0%

UVA116 单向TSP

题目链接

题目大意

给一个$m$行$n$列($m≤10,n≤100$)的整数矩阵,从第一列任何一个位置出发每次往右、右上、右下走一格,最终到达最后一列。要求经过的整数之和最小。整个矩阵是环形的,即第一行的上一行是最后一行,最后一行的下一行是第一行。输出路径上每列的行号。多解时输出字典序最小的。
最优路径

输入

每组的第1行:$m$和$n$,分别为行数和列数。
每组的第$2~m+1$行:每行$n$个数,用空格分开,代表整数矩阵。

输出

每组有两行,第一行是每列的行号,第二行是路径的经过的整数之和。

题解

题解参考紫书

很容易想到动态规划,设计出状态,d(i,j)表示从格子(i,j)出发到达最后一列需要的最低的开销,因为题目需要输出最优路径,所以记录下路径。

#include"bits/stdc++.h"
#define inf 100000001
using namespace std;
int main() {
    const int maxn=101;
    int n,m;
    while(~scanf("%d%d",&m,&n)&&m&&n) {
    int ans=inf,fst=0,next[maxn][maxn],a[maxn][maxn],d[maxn][maxn];
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++) {
            scanf("%d",&a[i][j]);
        }
    for(int j=n;j>0;j--)
        for(int i=1;i<=m;i++) {
            if(j==n) d[i][j]=a[i][j]; //递归边界
            else {
                int rows[3]={i,i-1,i+1};
                if(i==1) rows[1]=m; //因为第1行上面是第m行
                if(i==m) rows[2]=1; //同上
                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==1&&ans>d[i][j]) {ans=d[i][j];fst=i;}
        }
        printf("%d",fst);   //输出第一行
        for(int i=next[fst][1],j=2;j<=n;i=next[i][j],j++)
            printf(" %d",i);
        printf("\n%d\n",ans);
    }
        return 0;
}