該題是《算法競賽入門經典（第二版）》的一道例題，難度不算大。我先在沒看題解的情況下自己做了一遍，雖然最終通過了，思路與書上的也一樣。但比書上的代碼復雜了很多，可見自己對問題的處理還是有所欠缺。
該題類似於數字三角形問題，處理的方式就是從倒數第二列逐步推到第一列, 每次選擇其後一列權值最小的那條路徑。最終找到花費最小的那個即可。由於出現多個答案時要輸出字典序考前的路徑，所以在選擇路徑的時候如果出現相同，要選擇行數小的那個。我在處理這個問題時用了很多條件語句，使得最終的代碼很長。下面是我的代碼：
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4
5 using namespace std;
6
7 long long a[12][110];
8 int pre[12][110];
9
10 int main()
11 {
12 int m, n, i, j, temw, temr;
13
14 while(scanf("%d%d", &m, &n) == 2)
15 {
16 for(i = 1; i <= m; i++)
17 {
18 for(j = 1; j <= n; j++)
19 {
20 scanf("%lld", &a[i][j]);
21 }
22 }
23 memset(pre, 0, sizeof(pre));
24 for(j = n-1; j >= 1; j--)
25 {
26 for(i = 1; i <= m; i++)
27 {
28 //首先考慮向上方向的路徑
29 if(i == 1) //第一行，向上方向走到最後一行
30 {
31 temw = a[m][j + 1];
32 temr = m;
33 }
34 else
35 {
36 temw = a[i - 1][j + 1];
37 temr = i - 1;
38 }
39 //考慮向正前方向的路徑
40 if(a[i][j + 1] < temw)
41 {
42 temw = a[i][j + 1];
43 temr = i;
44 }
45 else if(a[i][j + 1] == temw)
46 {
47 temr = min(temr, i); //相等取行號小的。
48 }
49 //考慮向下方向的路徑
50 if(i == m) //最後一行，向下走到第一行
51 {
52 if(a[1][j + 1] < temw)
53 {
54 temw = a[1][j + 1];
55 temr = 1;
56 }
57 else if(a[1][j + 1] == temw)
58 {
59 temr = min(temr, 1);
60 }
61 }
62 else
63 {
64 if(a[i + 1][j + 1] < temw)
65 {
66 temw = a[i + 1][j + 1];
67 temr = i + 1;
68 }
69 else if(a[i + 1][j + 1] == temw)
70 {
71 temr = min(temr, i + 1);
72 }
73 }
74 a[i][j] += temw;
75 pre[i][j] = temr; //記錄路徑
76 }
77 }
78 temw = a[1][1];
79 temr = 1;
80 for(i = 2; i <= m; i++) //尋找最小的。
81 {
82 if(a[i][1] < temw)
83 {
84 temw = a[i][1];
85 temr = i;
86 }
87 }
88 //輸出路徑
89 if(n == 1)
90 {
91 printf("%d\n", temr);
92 }
93 else
94 {
95 for(i = temr, j = 1; j <= n-1;)
96 {
97 printf("%d ", i);
98 i = pre[i][j];
99 j++;
100 }
101 printf("%d\n", i);
102 }
103 printf("%lld\n", a[temr][1]);
104 }
105 return 0;
106 }
顯然，在處理三個方向時，用了很多代碼，而書上是這樣做的：
1 int rows[3] = {i, i-1, i+1}; //普通情況下的行號
2 if(i == 0) //書上第一行行號為0，如果是第一行，向上的行號需要改變。
3 rows[1] = m - 1; //最後一列列號為m-1
4 if(i == m-1)
5 rows[2] = 0;
6 d[i][j] = INF; //數組d用來存儲權值
7 sort(rows, rows+3); //先排序，再比較
8 for(int k = 0; k < 3; k++)
9 {
10 int v = d[rows[k]][j+1] + a[i][j];
11 if(v < d[i][j])
12 {
13 d[i][j] = v;
14 next[i][j] = rows[k];
15 }
16 }
顯然，書上通過先排序再比較，這樣從最小的行號開始，找最小權值，找到的最小權值一定是行號最小的，減小了很多代碼量。
還需要說的一點是，這道題我一開始看錯了題意！！！這是比賽的大忌! 根據所給的圖，想當然地以為是從第一行第一列開始走到最後一行最後一列。順便說一下這種情況的我的思路吧。這種情況下，需要一個bool型數組標記每個點是否可到達，首先標記終點可到達，然後從倒數第二列循環，選擇後一列中可以到達且權值最小，行號最小的一條路徑，並標記該點可到達，如果後面沒有可到達的點，就標記該點不可到達。循環到第一列時，只需要考慮起點即可。其他類似於原題。
