第5回ドワンゴからの挑戦状予選 C k-DMC https://atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_c
尺取りっぽくやるんだろうな~~と思いつつ具体的にどうやれば良いのかがわからなかった。尺取り苦手説ある。
ちなみに、尺取りっぽくやります。
ARC 064E Cosmic Rays https://atcoder.jp/contests/arc064/tasks/arc064_c
スタートとゴールに半径0のバリアを張り、バリアの中心を頂点として、
頂点AとBを結ぶ辺の長さ=2点間の距離-バリアAの半径-バリアBの半径
とした辺を全ての頂点の組の間に張る。
このグラフでスタートからゴールまでの最短距離をdijkstraで求めるとできる。