プリム法

ダイクストラでは、ずっと「頂点sからの距離が一番近い頂点を選び続ける」みたいな感じだった。

プリム法の場合だと「頂点sが含まれる島からの距離が一番近い頂点を選び続ける」みたいな感じになる。

ほとんどダイクストラ。vector<int> dist(n) が vector<bool> used(n) になるとかそういうレベル。