太巧妙了，只要做兩次 dijkstra 就可得到答案
Yu-Cheng Huang amoshyc
裸 MST。Kruskal 直接下了就是了
求最大擴張樹，一樣，Kruskal 直接用就是了
另外，該如何判斷 MST 不存在的情況呢？以下二個方法皆可行
求 MST 裡的最長邊，水題，Kruskal 是你的好朋友
求次短路徑……修改 Dijkstra，不只記錄到各點的最短距離（d[i]），還記錄次短距離（sd[i]）
實作上有幾點要注意（ 不確定這樣想對不對… ）：
得先看透這題是在考 MST……
將人當成節點，關係當成邊，我們能節省的最大成本就是這個圖裡的 MST（實際上，是最大生成森林）
sieve of Eratosthenes + BFS 沒什麼好說的
當
n = p[1]^a[1] * p[2]^a[2] * ... * p[m]^a[m]
擴展 sieve of Eratosthenes + 建前綴表
實作時注意，int 很容易溢位……建議用 long long