- UVA 116 --
- Unidirectional TSP
题意:
求从第一列到最后一列的一个字典序最小的最短路, 要求不仅输出最短路长度, 还要输出字典序最小的路径
解题思路:
设 d(i,j)为从格子 (i,j) 出发, 到最后一列的最小开销因为不仅要输出解, 还要输出字典序最小的序列, 所以需要再计算 d(i,j)的同时记录下一列的行号的最小值
- For each specification the number of rows will be between 1 and 10 inclusive;
- the number of columns will be between 1 and 100 inclusive.No paths weight will exceed integer values representable using 30 bits.#include < iostream > #include < algorithm > using namespace std;
- const int INF = 0x3f3f3f3f;
- const int maxi = 10 + 5;
- const int maxj = 100 + 5;
- int d[maxi][maxj];
- int a[maxi][maxj];
- int c[maxi][maxj]; /// 记录路径
- int main() {
- int m,
- n;
- while (cin >> m >> n) {
- for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) cin >> a[i][j];
- 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 rows[3] = {
- i,
- i - 1,
- i + 1
- };
- if (i == 0) rows[1] = m - 1; // 第 0 行上面是第 m-1 行
- if (i == m - 1) rows[2] = 0; // 最后一行下面是第 0 行
- sort(rows, rows + 3); // 重新排序, 以便找到字典序最小的
- d[i][j] = INF;
- for (int k = 0; k < 3; k++) {
- int v = d[rows[k]][j + 1] + a[i][j];
- if (v < d[i][j]) {
- d[i][j] = v;
- c[i][j] = rows[k];
- }
- }
- }
- if (j == 0 && d[i][j] < ans) {
- ans = d[i][j];
- first = i;
- }
- }
- }
- cout << first + 1;
- for (int i = c[first][0], j = 1; j < n; i = c[i][j], j++) cout << " " << i + 1;
- cout << endl << ans << endl;
- }
- return 0;
- }
测试样例:
- 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
- 2 2
- 9 10
- 9 10
- 10 14
- 1 2 2 1 1 1 1 1 1 1 1 1 1 2
- 1 1 2 2 1 1 1 1 1 1 1 1 1 1
- 1 1 1 2 2 1 1 1 1 1 1 1 1 1
- 1 1 1 1 2 2 1 1 1 1 1 1 1 1
- 1 1 1 1 1 2 2 1 1 1 1 1 1 1
- 1 1 1 1 1 1 2 2 1 1 1 1 1 1
- 1 1 1 1 1 1 1 2 2 1 1 1 1 1
- 1 1 1 1 1 1 1 1 2 2 1 1 1 1
- 1 1 1 1 1 1 1 1 1 2 2 1 1 1
- 1 1 1 1 1 1 1 1 1 1 2 2 1 1
- 4 7
- 1 2 -3 4 -2 1 5
- -1 3 5 -2 6 -3 4
- 2 1 3 -2 -1 3 1
- 3 -3 4 2 -3 4 3
- 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
- 2 2
- 9 10
- 9 10
- 5 6
- 1 1 1 1 1 1
- 2 2 2 2 2 2
- 3 3 3 3 3 3
- 4 4 4 4 4 4
- 5 5 5 5 5 5
- 3 4
- 1 2 3 4
- 1 2 3 4
- 1 2 3 4
- 5 5
- 1 5 10 6 3
- 5 1 8 4 11
- 10 12 5 2 9
- 7 3 20 5 8
- 4 1 5 12 6
- 5 10
- 11 53 34 73 18 53 99 52 31 54
- 4 72 24 6 46 17 63 82 89 25
- 67 22 10 97 99 64 33 45 81 76
- 24 71 46 62 18 11 54 40 17 51
- 99 8 57 76 7 51 90 92 51 21
- 5 10
- 11 53 1 73 18 53 99 52 31 54
- 4 72 54 6 46 17 63 82 89 25
- 67 22 80 97 99 64 33 45 81 76
- 24 71 46 62 18 11 54 40 17 51
- 99 8 57 76 7 51 90 92 51 21
- 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
- 10 100
- 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
- 4 29
- 1 -1 0 0 1 -1 -1 -1 1 1 0 1 -1 -1 -1 0 -1 -1 1 -1 1 0 0 -1 0 -1 1 1 0
- -1 1 0 -1 -1 0 1 0 -1 -1 -1 -1 1 1 0 -1 -1 0 -1 -1 1 -1 1 0 -1 1 0 1 -1
- 0 0 1 0 -1 1 0 0 1 1 0 -1 1 1 -1 -1 1 0 0 1 1 0 -1 1 0 -1 -1 1 1
- 1 -1 -1 -1 -1 -1 0 0 0 1 -1 0 0 0 -1 -1 0 -1 0 1 0 -1 1 0 1 1 -1 0 1
- 1 1
- 1
结果:
- 1 2 3 4 4 5
- 16
- 1 2 1 5 4 5
- 11
- 1 1
- 19
- 1 2 3 4 5 6 7 8 9 10 1 1 1 2
- 14
- 1 4 1 2 1 2 3
- -11
- 1 2 3 4 4 5
- 16
- 1 2 1 5 4 5
- 11
- 1 1
- 19
- 1 1 1 1 1 1
- 6
- 1 1 1 1
- 10
- 1 2 3 2 1
- 14
- 2 3 3 2 1 2 3 4 4 5
- 188
- 1 5 1 2 1 2 3 4 4 5
- 172
- 4 3 2 3 3 4
- -49
- 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
- 100
- 2 1 4 4 3 4 1 1 2 2 2 2 1 1 1 2 1 1 2 1 4 4 1 1 2 1 4 1 2
- -25
- 1
- 1
来源: http://www.bubuko.com/infodetail-2506933.html