UVA 116 -- Unidirectional TSP(DP)

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 path’s weight will exceed integer values representable using 30 bits.

 1 #include<iostream>
 2 #include<algorithm> 
 3 using namespace std;
 4 const int INF = 0x3f3f3f3f;
 5 const int maxi = 10+5;
 6 const int maxj = 100+5;
 7 int d[maxi][maxj];
 8 int a[maxi][maxj];
 9 int c[maxi][maxj];///记录路径 
10 
11 int main()
12 {
13     int m,n;
14     while(cin>>m>>n){
15         for(int i=0;i<m;i++)
16             for(int j=0;j<n;j++)
17                 cin>>a[i][j];
18         int ans = INF,first = 0;
19         for(int j=n-1;j>=0;j--){//列 
20             for(int i=0;i<m;i++){
21                 if(j == n-1){//最右边一列 
22                     d[i][j] = a[i][j];
23                 }
24                 else{
25                     int rows[3] = {i,i-1,i+1};
26                     if(i == 0) rows[1] = m-1;//第0行“上面”是第m-1行 
27                     if(i == m-1) rows[2] = 0;//最后一行“下面”是第0行 
28                     sort(rows,rows+3);//重新排序，以便找到字典序最小的 
29                     d[i][j] = INF;
30                     for(int k = 0;k<3;k++){
31                         int v = d[rows[k]][j+1] + a[i][j];
32                         if(v < d[i][j]) {
33                             d[i][j] = v;c[i][j] =  rows[k];
34                         }
35                     }
36                 }
37                 if(j == 0 && d[i][j]<ans){
38                     ans = d[i][j];first = i;
39                 }
40             }
41         }
42         
43         cout<<first+1;
44         for(int i=c[first][0],j=1;j<n;i = c[i][j],j++)
45             cout<<" "<<i+1; 
46         cout<<endl<<ans<<endl;
47     }
48     
49     return 0;
50  }

测试样例：
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