文件名称：单向最小权路径（包含c++源程序）
文件大小：38KB
文件格式：DOC
更新时间：2012-04-23 17:25:06
单向最小权路径 最小权 最小路径 单向TSP
题目如下：包含源程序（可以运行的c++程序） Description 一个 m 行 n 列的整数矩阵上的一条路径是指矩阵元素的下标序列 (i1,1), (i2,2), ..., (in,n), 其中 1 ≤ i1 ≤ m, 且 | ij+1－ij | ≤ 1, j = 1, 2, ..., n-1. 也就是说, 路径中每个元素的行号是前一个元素(如果存在的话)的行号或者加 1、减 1. 由于列下标是自然序的, 所以为方便起见, 只用行下标序列 i1, i2, ..., in 表示对应路径. 如果前一个元素的行号是 1, 则后一个元素的行号是 1, 2 或 m. 如果前一个元素的行号是 m, 则后一个元素的行号是 1, m-1, m. 一条路径上的元素和称为此路径的权. 本题要求对于给定的整数矩阵, 计算其具有最小权的路径及相应的权. Input 有多个测试用例. 每个测试用例的第一行是两个正整数 m(1 ≤ m ≤ 10) 和 n(1 ≤ n ≤ 100), 然后是 m 行, 每行 n 个绝对值不超过 109 的整数, 表示 m*n 阶整数矩阵. 输入直至没有数据为止. Output 对于每个测试用例, 输出两行. 第一行是具有最小权的路径(如果有多条路径具有最小权, 则输出按字典序最小者), 第二行是对应的最小权. Sample Input 5 6 3 4 1 2 8 6 6 1 8 2 7 4 5 9 3 9 9 5 8 4 1 3 2 6 3 7 2 8 6 4 5 6 3 4 1 2 8 6 6 1 8 2 7 4 5 9 3 9 9 5 8 4 1 3 2 6 3 7 2 1 2 3 Sample Output 1 2 3 4 4 5 16 1 2 1 5 4 5 11 Hint 在 Sample 中的第二例, 1 2 1 5 5 5 也具有最小权 11, 但按字典序它不是最小的