ARC064 E - Cosmic Rays
解法
あるバリア内は好きな座標に移動できます。
ので、あるバリアから、別のバリアへと移動することを考えます。
そのとき、2つのバリアについて重複する箇所が存在すれば、そのバリア同士は自由に行き来することができます。そうでないときは、2つの円の最短距離を求めれば、その距離の部分のみ、宇宙線を浴びることになります。それよりも短い距離で2つのバリアを行き来することはできません。
結局、2つのバリアの距離は、
で求めることができ、また、2つのバリアで重複箇所がある場合は、この値が0以下になるので、最終的に、2つのバリアを行き来する際に浴びる宇宙線の時間は
となります。
スタート地点、ゴール地点は、中心座標そのまま、半径が0の円とみなすことができるので、あとは、個のバリアについて、任意のバリアのペアを行き来した際に浴びる宇宙線の時間を計算してそれをコストとしつつ、ダイクストラ法を用いることで、スタート地点からゴール地点へ行く際に浴びる宇宙線の時間の最小値が求まります。
