c100. Unidirectional TSP＠Morris' Blog｜PChome Online 個人新聞台

2011-06-21 10:06:13| 人氣974| 回應0 | 上一篇 | 下一篇

c100. Unidirectional TSP

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

給你一個由整數組成的 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

提示：

* 中文翻譯：Lucky 貓

出處：

ACM 116

作法 : 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;
}

我要檢舉

#c100#Unidirectional TSP

台長： Morris

您可能對以下文章有興趣

[UVA][DP] 1213 - Sum of Different Primes

[UVA] 927 - Integer Sequences from Addition of Terms

[UVA][TSP] 10944 - Nuts for nuts..

[UVA][高斯消去] 12143 - Stopping Doom's Day

人氣(974) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:c093. Counterfeit Dollar
此分類上一篇:d686. Q10003: Cutting Sticks

回應(0)