內容
問題敘述
星光遊樂園擁有全球最大的自動迷宮，迷宮內有 m 個可能的藏寶點，但每次重新設定迷宮時最多只有 n 個藏寶點藏有寶物，且迷宮的路徑也可以做改變。尋寶者如果在一定的時間內找到所有的寶物才能兌換與寶物等值的園區消費卷。消費卷兌換額與尋找寶物過程中所走過的路徑距離成反比。換句話說，走過的路徑距離越短，找到所有寶物後，所能換得的消費卷額就越高。為了確保園區營運正常，發出去的消費卷必須有所拿捏。因此經營者希望能夠在每次迷宮設定好後，自動算出從迷宮入口出發，找到所有寶物，最後至迷宮出口所需的最短路徑距離，好依此數據設定消費卷兌換的準則。請寫一程式來計算此最短路徑距離。
條件說明
1. 迷宮內的可能藏寶點數 m, 2 ≤ m ≤ 20。可能藏寶點的代號為 1, 2, 3, …,
n。迷宮起始點代號為 1，迷宮出口點代號為 m。
2. 迷宮內的實際藏寶數為 n, 2 ≤ n ≤ 15。
3. 迷宮內的點對點路徑距離最短為 1，最長為 10。
星光遊樂園擁有全球最大的自動迷宮，迷宮內有 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。
個整數，分別代表實際藏寶點的代號。接下來的 m 行（第3 行至第3+(m-1)行）
記錄該迷宮路徑的資訊：每一行都有 m 個整數，整數之間以一個空白隔開；第 i
行的第 j 個整數代表可能藏寶點 i 到可能藏寶點 j 的距離（與 j 到 i 的距
離相同）。若兩個可能藏寶點之間沒有直接相連的路徑，則以 0 代表之。任一可
能藏寶點到自己的距離也是 0。
輸出說明
請輸出一整數，即從迷宮入口出發，找到所有寶物，最後至迷宮出口所需的最短路徑距離。
範例輸入
#1
輸入範例 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
輸出範例 1 15 輸出範例 2 6
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (20%): 2.0s , <1K
公開 測資點#1 (20%): 2.0s , <1K
公開 測資點#2 (20%): 2.0s , <1K
公開 測資點#3 (20%): 2.0s , <1K
公開 測資點#4 (20%): 2.0s , <1K
公開 測資點#0 (20%): 2.0s , <1K
公開 測資點#1 (20%): 2.0s , <1K
公開 測資點#2 (20%): 2.0s , <1K
公開 測資點#3 (20%): 2.0s , <1K
公開 測資點#4 (20%): 2.0s , <1K
提示 ：
輸入範例 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
(太威啦)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||