515.1

続き。

1000

二次元平面上に二点取り、それ以外の任意の点について、それら三点からの距離の合計が最小になる点までの合計距離を求める問題。

三点目の点はかなりたくさんあって、全部について、集合する点をいちいち決められない状況なので、同時にまとめて求めることを考える。三点からの距離の合計は、min(二点から集合する点への距離の合計+その点から三点目への距離)であり、前半部をあらかじめ全部の可能な集合する点について求めておく。後は三点目への距離を、全部の点を開始点にじわじわ広げて求めていく。このとき、小さい方から計算していくので、本質的にはダイクストラになる。

実際には最初の二点の選択が400通りくらいあって、その分だけやらないといけないので、メモリ制約とかに注意が必要。(下手にやると容量が不足してかなりGCが連発される...。)