首页 > 代码库 > UVa 116 (多段图的最短路) Unidirectional TSP
UVa 116 (多段图的最短路) Unidirectional TSP
题意：
有一个m行n列的正整数环形矩阵(即矩阵第一行的上一行是最后一行，最后一行的下一行是第一行)，从第一列的任意位置出发，每次只能向右，右上，右下三个方向行走，输出路径及路径上所有数之和的最大值，多解时输出最小字典序的解。
分析：
这道题有点像数塔的变形，不同的是从三角形变成了矩形。依然是从最后一列往前递推。Next数组时用来记录路径的，first是最优解的第一列的行号。代码中将下一行的三个拓展出的行号排序来保证字典序最小。
1 #include <cstdio> 2 #include <algorithm> 3 4 const int maxm = 15; 5 const int maxn = 100 + 5; 6 const int INF = 1000000000; 7 int m, n, d[maxm][maxn], a[maxm][maxn], next[maxm][maxn]; 8 9 int main(void)10 {11 //freopen("116in.txt", "r", stdin);12 while(scanf("%d%d", &m, &n) == 2)13 {14 int ans = INF, first = 0;15 for(int i = 0; i < m; ++i)16 for(int j = 0; j < n; ++j)17 scanf("%d", &a[i][j]);18 for(int j = n-1; j >= 0; --j)19 {20 for(int i = 0; i < m; ++i)21 {22 if(j == n-1) d[i][j] = a[i][j]; //±ß½ç23 else24 {25 int row[3] = {i-1, i, i+1};26 if(i == 0) row[0] = m-1;27 if(i == m-1) row[2] = 0;28 std::sort(row, row + 3); //ÅÅÐòÒÔ±£Ö¤×ÖµäÐò×îС29 d[i][j] = INF;30 for(int k = 0; k < 3; ++k)31 {32 int v = d[row[k]][j+1] + a[i][j];33 if(v < d[i][j])34 {35 d[i][j] = v;36 next[i][j] = row[k];37 }38 }39 }40 if(j == 0 && d[i][j] < ans)41 {42 ans = d[i][j];43 first = i;44 }45 }46 }47 printf("%d", first+1);48 int i = next[first][0];49 for(int j = 1; j < n; ++j)50 {51 printf(" %d", i+1);52 i = next[i][j];53 }54 printf("\n%d\n", ans);55 }56 57 return 0;58 }
UVa 116 (多段图的最短路) Unidirectional TSP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。