在此先感謝 p3a_owhj 對於本題n的說明

題目說n=8不一定代表有8個點

而是出現的節點範圍是W1、W2...W8

所以很有可能n=8  但卻只出現W2、W3、W5

再來題目說找最小路徑實際上就是建立一個最小生成樹

我這裡是用Kruskal演算法

將邊的權重從小大到排列，再依序選取邊，若選取的邊會形成迴圈就不要選這個邊

(可以用參考演算法筆記的 disjoint set forest 利用樹根來判斷節點是否在同一集合)

選出節點數目-1個邊後就可以跳出來停止選取

而節點數目-1個邊的排列是用字典排列

舉例

若答案的邊有

W2 W7

W9 W6

W4 W5

則字典排序後為

W2 W7

W4 W5

W9 W6