(UVa116)单向TSP(Unidirectional TSP)

发表于 | 分类于 ，

打印路径的dp思路

题目描述:

给出一个m*n(m<=10,n<=100)的矩阵, 从第一列的某一位置出发, 每次向右,右上或右下走一格, 最终到达最后一列, 整个矩阵是环形的, 要求经过的整数和最小, 输出最优解及路径所经过的行号

思路:

多段图dp

因为要求路径, 所以设d(i,j)为以(i,j)为起点的最短路径和, 用nxt(i,j)表示路径上下一列的行号

则答案为min{d(k,1)}(1<=k<=n)

状态转移方程见代码

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstdio>
#include <climits>
#include <cstring>
#include <algorithm>
using namespace std;
const int Mm(25);
const int Mn(105);
int nxt[Mm][Mn];
int mp[Mm][Mn],d[Mm][Mn]; //mp表示(i,j)上的值
int main()
{
    int m,n;
    while(scanf("%d %d",&m,&n)==2) //多组数据输入
    {
        memset(mp,0,sizeof mp);
        for(int i(1);i<=m;++i)
            for(int j(1);j<=n;++j)
                scanf("%d",&mp[i][j]);
        memset(d,0x3f,sizeof d);
        memset(nxt,0,sizeof nxt);
        for(int i(1);i<=m;++i)
            d[i][n] = mp[i][n]; //初始化d(i,n)
        for(int i(n-1);i>=1;--i)
        {
            for(int j(1);j<=m;++j)
            {
                int nr[3] = {j,j-1,j+1};
                if(j==1) nr[1] = m;
                if(j==m) nr[2] = 1;
                sort(nr,nr+3); //按字典序选择决策
                for(int k(0);k<3;++k)
                {
                    if(d[nr[k]][i+1]+mp[j][i]<d[j][i])
                    { d[j][i] = d[nr[k]][i+1]+mp[j][i]; nxt[j][i] = nr[k]; } //更新当前最优解
                }
            }
        }
        int ans(INT_MAX), p(0);
        for(int i(1);i<=m;++i) //搜索最优解
            if(d[i][1]<ans)
            { ans=d[i][1]; p=i; }
        for(int i(1);i<=n;++i) //打印路径
        {
            if(i!=1) cout << " ";
            cout << p;
            p = nxt[p][i];
        }
        cout << endl << ans << endl;
    }
    return 0;
}