UVa116 Unidirectional TSP 多段图的最短路

向右看齐 2021-12-19 02:25 212阅读 0赞

## 题意：给定一个n\*m的矩阵，要求从第一列的任何一行出发，每次沿右或右下或右上到达后面一列，最后到第m列任何一行整个路程的最小值，并且要求是字典序最小的。 ##

## 分析：阶段很明显，一列便是一个阶段，在一列的每一个状态都有3种决策，右，右下，右上，直接更新最小值就行了。注意题目要求字典序最小，如果顺推，定义dp\[i\]\[j\]为在第i行第j列时走过的路程的最小值，发现后面难以求取字典序最小的方案，路径根本不好记录，就算记录了路径，也要进行逆向打印，逆推就很方便了。用d(i,j)表示从格子(i,j)出发到最后一列的最小开销，则在(i,j)处有三种决策,d(i,j)转移到d(i-1,j+1),d(i,j+1),d(i+1,j+1),还需要一个数组来记录每一步决策过程。 ##

## 代码： ##

#include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn = 100 + 5;
    const int INF = 1000000000;
    int m, n, a[maxn][maxn], d[maxn][maxn], next[maxn][maxn];
    
    int main()
    {
        while(scanf("%d%d", &m, &n) == 2 && m)
        {
            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;
    }