復習帳

とにかく和訳

TopCoder

問題はこちら

TopCoder | Login

「王国X都市と村など」

格子王国が平面上に存在している。

王国にはNの都市とMの村が存在ている。

ｉ番目の都市の座標は(cityX[i], cityY[i])で与えられる。

同様にｉ番目の村の座標は(villageX[i], villageY[i])で与えられる。

王国に道は存在せず、村は王国内のどの都市とも繋がっていない、これを改善したい。

次の３つの手順を繰り返すことで、全ての村を都市につなげたい。

どの都市にも繋がっていない村に対して、

１：どことも繋がっていない村を１つ取り上げ、これをVとする。

2：都市もしくは「既に都市と繋がっている村」の座標を取り上げ、これをXとする。

3:VとX間に道を作る。この道の長さは、VとXの間のユークリッド距離に等しい。

この手順を、全ての村が都市と繋がるまで繰り返す。

道の長さの合計を算出し、その最小値を返せ。

参考：ユークリッド距離

Permalink | コメント(0) | トラックバック(0) | 11:28