Morris' Blog

2011-08-25 13:26:29Morris

d598. 3. 尋寶問題 (普通製造版)

留言 0 收藏 0 推薦 0

內容：

問題敘述
星光遊樂園擁有全球最大的自動迷宮，迷宮內有 m 個可能的藏寶點，但每次重
新設定迷宮時最多只有 n 個藏寶點藏有寶物，且迷宮的路徑也可以做改變。尋
寶者如果在一定的時間內找到所有的寶物才能兌換與寶物等值的園區消費卷。消
費卷兌換額與尋找寶物過程中所走過的路徑距離成反比。換句話說，走過的路徑
距離越短，找到所有寶物後，所能換得的消費卷額就越高。為了確保園區營運正
常，發出去的消費卷必須有所拿捏。因此經營者希望能夠在每次迷宮設定好後，
自動算出從迷宮入口出發，找到所有寶物，最後至迷宮出口所需的最短路徑距
離，好依此數據設定消費卷兌換的準則。請寫一程式來計算此最短路徑距離。
條件說明
1. 迷宮內的可能藏寶點數 m, 2 ≤ m ≤ 20。可能藏寶點的代號為 1, 2, 3, …,
n。迷宮起始點代號為 1，迷宮出口點代號為 m。
2. 迷宮內的實際藏寶數為 n, 2 ≤ n ≤ 15。
3. 迷宮內的點對點路徑距離最短為 1，最長為 10。

輸入說明：

第一行有兩個整數 m, n，分別代表可能藏寶位置數及實際藏寶數。第二行有 n
個整數，分別代表實際藏寶點的代號。接下來的 m 行（第3 行至第3+(m-1)行）
記錄該迷宮路徑的資訊：每一行都有 m 個整數，整數之間以一個空白隔開；第 i
行的第 j 個整數代表可能藏寶點 i 到可能藏寶點 j 的距離（與 j 到 i 的距
離相同）。若兩個可能藏寶點之間沒有直接相連的路徑，則以 0 代表之。任一可
能藏寶點到自己的距離也是 0。

輸出說明：

請輸出一整數，即從迷宮入口出發，找到所有寶物，最後至迷宮出口所需的最短路徑距離。

範例輸入：

輸入範例 1
6 3
2 3 6
0 1 2 4 0 0
1 0 0 0 7 0
2 0 0 0 0 0
4 0 0 0 2 5
0 7 0 2 0 4
0 0 0 5 4 0

輸入範例 2
4 2
1 2
0 5 1 4
5 0 2 5
1 2 0 1
4 5 1 0

範例輸出：

輸出範例 1
15

輸出範例 2
6

提示：

輸入範例 1 說明:

共有5 個藏寶點，其中3 個藏有寶物
藏寶點 2, 3, 6 藏有寶物，如下圖

輸入範例 2 說明

共有4 個藏寶點，其中2 個藏有寶物
藏寶點 1, 2 藏有寶物，如下圖

輸出範例 1 說明

路徑可為 1 2 1 3 1 4 6 或 1 3 1 2 1 4 6

輸出範例 2

說明
路徑為 1 3 2 3 4

出處：

98全國賽 (管理：swda289346)

作法 : A* Algorithm

用一個二進制, 0 代表沒經過的點 1 代表經過的點, 再來, 紀錄這個最後移動過的點,
次來, 紀錄這個狀態的最小值, 接著是主要的 H() 估計,
H() = 該點到終點的最短距離 + (未發現的點個數-1)
重覆狀態, 我仍然重覆丟入 Heap 中, 每次抓最小的出來做擴張

/**********************************************************************************/
/* Problem: d598 "3. 尋寶問題" from 98全國賽                              */
/* Language: C                                                                   */
/* Result: AC (20ms, 2750KB) on ZeroJudge                                        */
/* Author: morris1028 at 2011-08-25 13:20:34                                     */
/**********************************************************************************/

#include<stdio.h>
#include<string.h>
#define oo 40000
int Trea[21], n, m;
int map[21][21], F[21][21];
struct Heap {
    int hv, status, v;
    char find, last;
}Heap[2000000];/*min heap*/
int L;
void Floyd() {
   int a, b, c;
   for(a = 1; a <= n; a++) {
       for(b = 1; b <= n; b++) {
           F[a][b] = map[a][b];
           if(F[a][b] == 0)   F[a][b] = oo;
           if(a == b) F[a][b] = 0;
       }
   }
   for(a = 1; a <= n; a++)
       for(b = 1; b <= n; b++)
           for(c = 1; c <= n; c++)
               if(F[b][a]+F[a][c] < F[b][c])
                   F[b][c] = F[b][a]+F[a][c];
}
void Swap(int P, int S) {
    int T;
    T = Heap[P].hv, Heap[P].hv = Heap[S].hv, Heap[S].hv = T;
   T = Heap[P].v, Heap[P].v = Heap[S].v, Heap[S].v = T;
    T = Heap[P].status, Heap[P].status = Heap[S].status, Heap[S].status = T;
    T = Heap[P].last, Heap[P].last = Heap[S].last, Heap[S].last = T;
    T = Heap[P].find, Heap[P].find = Heap[S].find, Heap[S].find = T;
}
void siftup (int site) {
    int S = site, P = site >> 1;
    while(S >= 2 && Heap[P].hv > Heap[S].hv)
        Swap(P, S), S = P, P = S >> 1;
}
void siftdown(int site) {
    int P = site, S = site << 1;
    while(S <= L) {
        if(S < L && Heap[S+1].hv < Heap[S].hv)    S++;
        if(Heap[P].hv <= Heap[S].hv)    break;
        Swap(P, S), P = S, S = P << 1;
    }
}
void insHeap(int site, int hv, int v, int last, int find, int status) {/*insert new node*/
   Heap[site].hv = hv;
    Heap[site].v = v;
   Heap[site].last = last;
    Heap[site].find = find;
   Heap[site].status = status;
    siftup(site);
}
void delHeap() {/*delete last node*/
    Swap(1, L), L--;
    siftdown(1);
}
int H(int now, int find) {
    return F[now][n]+(m-find-1);
}
main() {
   while(scanf("%d %d", &n, &m) == 2) {
       int a, b, find = 0, x;
       for(a = 0; a < m; a++)
           scanf("%d", &Trea[a]);
       for(a = 1; a <= n; a++)
           for(b = 1; b <= n; b++)
               scanf("%d", &map[a][b]);
       Floyd(), L = 0;
       for(a = 0; a < m; a++) {
           L++, insHeap(L, F[1][Trea[a]]+H(Trea[a], 1), F[1][Trea[a]], a, 1, 1<<a);
       }
       int final = (1 << m)-1;
       int status, status_v, status_last, status_find;
       int tmp_status, tmp_status_v, Ans = -1;
       while(L) {
           status = Heap[1].status, status_v = Heap[1].v;
           status_last = Heap[1].last, status_find = Heap[1].find;
           if(status == final) {
               Ans = status_v + F[Trea[status_last]][n];break;
           }
           delHeap();
           for(b = 0; b < m; b++) {
               if((status & (1<<b)) == 0) {
                   tmp_status = status | (1<<b);
                   tmp_status_v = status_v + F[Trea[status_last]][Trea[b]];
                   L++, insHeap(L, tmp_status_v+H(Trea[b], status_find+1), tmp_status_v, b, status_find+1, tmp_status);
               }
           }
       }
       printf("%d\n", Ans);
   }
   return 0;
}

上一篇：d598. 3. 尋寶問題 (粗糙濫造版本)

下一篇：d429. 第一題: 社團分組 (club)

Morris' Blog

d598. 3. 尋寶問題 (普通製造版)

你可能感興趣的文章

第92天

老照片的故事~國防部女青年工作大隊22期結訓了

供奉

美西奇幻旅程記行

2025奇幻【冰島】走訪【金環之旅】4個景點一起看