まずは村の境界線を決めるために、凸包を作ります。凸包はAndrew ScanやGraham Scanを適用することができますが、点の数Vが最大100個なので、愚直なアルゴリズムを適用することもできます。
次に、 凸包上の点(集落)を順番にたどっていき、隣り合う節点の距離を足し合わせます(境界線上には必ず道がなければいけないため)。境界線上の節点をすべてまとめて一つの節点とみなして、最小全域木をKruscal法やPrim法で求め、辺の長さを足すことで道の長さを最小化することができます。