c100. Unidirectional TSP
內容 ：
給你一個由整數組成的 m*n 方陣，你必須要寫個程式，來計算出「重量」（ weight ） 最小的路線。每條路線都是從第一直行的任何一格做為起點，走了若干步之後，至第 n 行（最後一行）的其中一格為終點。所謂的一步就是從第 i 行走至第 i+1 行，其中移動的時候只能走到原本的或是相鄰的一橫列（也就是走平的或是斜一格）。另外要注意的是，第一橫列和最後一橫列（第 m 列）也算是相鄰的，也可以這樣想，就是整個方陣是上下「包」起來的，看起來像一個倒著的圓柱體。總之，對於任何一格能夠走的下一步就如下圖所示：
所謂一個路徑的「重量」（weight）就是此路徑經過的 n 個格子裡，它們的整數總和。舉個例子，下面有兩個不同的5*6 方陣。（實際上你可以注意到它們的不同只在最後一列而已）
這兩個方陣的「最小重量路徑」（ minimal-weight path ）已經在上面分別標出來了。注意一下右邊的方陣，其利用了第一列和最後一列是相鄰的這個性質達到了最小的重量。
輸入說明
：
輸入裡包含多組測試資料，每組代表一個方陣。每組測試資料的第一列為2個正整數 m 與 n （1 <= m <=10，1 <= n <= 100），依序表示這方陣有幾橫列和幾直行。而後就是 m*n 個整數，這些整數是按照「列順序」（ row major order ）來排列，也就是輸入裡的前 n 個數表示方陣的第一橫列，再下來的 n 個數表示第二橫列，依此類推。在輸入裡，同一列的數彼此間將會被一個以上的空白隔開。值得注意的是，這裡說的整數並不一定是正的。輸入以及計算的過程所出現的數均不會超過長整數（long）的範圍。
Sample Input中前2組測試資料所表達的方陣就是上方的2個圖，請參考。
輸出說明
：
對於每個方陣，你必須輸出兩列東西。第一列是「最小重量路徑」（ minimal-weight path ），第二列則是其「重量」。對於第一列，你必須輸出 n 個正整數，依序表示在每一行，此路徑經過了第幾列。如果存在兩個以上的路徑其「重量」皆為最小，則輸出按照字典順序（ lexicographically ）最小的那一個路徑。請參考Sample Output。
範例輸入 ：
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
範例輸出 ：
1 2 3 4 4 5 16 1 2 1 5 4 5 11 1 1 19
提示
：
出處
：
作法 : DP
邊做最佳值的更新時，同時紀錄最佳值從哪裡來
/**********************************************************************************/
/* Problem: c100 "Unidirectional TSP" from ACM 116 */
/* Language: C */
/* Result: AC (4ms, 276KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-20 14:17:37 */
/**********************************************************************************/
#include<stdio.h>
#define Maxv 10000000
main() {
int n, m;
while(scanf("%d %d", &n, &m) == 2) {
int Map[10][100], a, b, c, min;
int next[10][100], t[3];
for(a = 0; a < n; a++)
for(b = 0; b < m; b++)
scanf("%d", &Map[a][b]);
for(b = m-2; b >=0; b--) {
for(a = 0; a < n; a++) {
min = Maxv;
t[0] = (a+n-1)%n, t[1] = a, t[2] = (a+1)%n;
for(c = 0; c < 3; c++) {
if(min > Map[t[c]][b+1])
min = Map[t[c]][b+1], next[a][b] = t[c];
else if(min == Map[t[c]][b+1])
next[a][b] = (next[a][b] < t[c]) ? next[a][b] : t[c];
}
Map[a][b] += min;
}
}
min = Maxv;
int st = 0;
for(a = 0; a < n; a++)
if(min > Map[a][0]) {
min = Map[a][0], st = a;
}
printf("%d", st+1);
for(a = 0; a < m-1; a++) {
printf(" %d", next[st][a]+1);
st = next[st][a];
}
printf("\n%d\n", min);
}
return 0;
}