本文主要是介绍例题9-4 UVa116 Unidirectional TSP（DP:多段图的最短路），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
看白书
要点：
一共三种决策：直行，右上，右下。那么就递推，注意题目中可以从第一列的任意一行出发，而且是环形的，最后还得按字典序输出路径，路径输出就直接用数组记录，因为是倒序递推，所以正序直接可以得到路径。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m;
int a[30][300], d[30][300];
int nex[30][300];void dp()
{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 row[3] = { i,i - 1,i + 1 };if (i == 0)row[1] = m - 1;if (i == m - 1)row[2] = 0;sort(row, row + 3);//先排序可以确保优先选择字典序小的行d[i][j] = inf;for (int k = 0; k<3; k++)//这里求三种决策的最优解{int v = d[row[k]][j+1] + a[i][j];if (d[i][j]>v){d[i][j] = v;nex[i][j] = row[k];//路径记录，因为是逆序的，所以反向就直接是正序}}}if (j == 0 && ans > d[i][j])//这里求从第一列的哪一行出发的最优解{ans = d[i][j];first = i;}}}printf("%d", first + 1);int i = nex[first][0];for (int j = 1; j < n; j++)//正序输出的就是路径{printf(" %d", i + 1);i = nex[i][j];}printf("\n%d\n", ans);
}
int main()
{while (scanf("%d%d", &m, &n) != EOF)//注意行列输入对应的m和n{for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)scanf("%d", &a[i][j]);dp();}return 0;
}这篇关于例题9-4 UVa116 Unidirectional TSP（DP:多段图的最短路）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
