a153. TOI 2024/12 潛力組：超能星球

題目描述

一顆星球有 12 個面，編號為 1 到 12。人在星球表面移動時，只能跨越相鄰兩面的公共邊；每跨越一條邊，都要支付該邊的能量成本，兩個方向的成本相同。

給定起點面 S、目的地面 T 與 30 條邊的成本，求從 S 到 T 的最低總成本。以下列出每條邊連接的兩個面，完整指定星球的相鄰關係：

• 邊 1：面 1 與面 2
• 邊 2：面 1 與面 3
• 邊 3：面 1 與面 4
• 邊 4：面 1 與面 5
• 邊 5：面 1 與面 6
• 邊 6：面 2 與面 3
• 邊 7：面 3 與面 4
• 邊 8：面 4 與面 5
• 邊 9：面 5 與面 6
• 邊 10：面 6 與面 2
• 邊 11：面 2 與面 9
• 邊 12：面 2 與面 8
• 邊 13：面 3 與面 8
• 邊 14：面 3 與面 7
• 邊 15：面 4 與面 7
• 邊 16：面 4 與面 11
• 邊 17：面 5 與面 11
• 邊 18：面 5 與面 10
• 邊 19：面 6 與面 10
• 邊 20：面 6 與面 9
• 邊 21：面 7 與面 8
• 邊 22：面 8 與面 9
• 邊 23：面 9 與面 10
• 邊 24：面 10 與面 11
• 邊 25：面 11 與面 7
• 邊 26：面 7 與面 12
• 邊 27：面 8 與面 12
• 邊 28：面 9 與面 12
• 邊 29：面 10 與面 12
• 邊 30：面 11 與面 12

輸入格式

第一行為 S、T，1 ≤ S、T ≤ 12，且 S ≠ T。 接下來 6 行，每行 5 個整數，依序為 C1 到 C30；Ci 是跨越第 i 條邊的成本，1 ≤ Ci ≤ 1000000。

輸出格式

輸出從面 S 到面 T 所需的最低總成本。

來源

TOI 2024 年 12 月潛力組〈超能星球〉。題意依官方規格重新撰寫，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202412/Planet.pdf