(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;
}