a111. TOI 2022/03 潛力組：士兵排列

題目描述

N 名士兵的編號是 1 到 N，要排成一列。若編號 i 與 j 的士兵相鄰，會產生 Aij 的衝突值；整個隊列的衝突值是所有相鄰士兵對的衝突值總和。

請找出總衝突值最小的排列。如果有多個最佳排列，選字典序最小者：由左到右比較，第一個不同位置上編號較小的排列優先。

輸入格式

第一行是 N，接著 N 行每行 N 個整數，為矩陣 A。

• 1 ≤ N ≤ 17
• 0 ≤ Aij ≤ 100
• Aij = Aji，且 Aii = 0

輸出格式

第一行輸出最小總衝突值。第二行輸出最佳排列的 N 個士兵編號，以空白隔開。

來源

TOI 2022 年 3 月潛力組〈士兵排列〉。以自寫文字重述，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202203/Soldiers.pdf 題意核對鏡像：https://zerojudge.tw/ShowProblem?problemid=h663