半年近く虚無をしていました
E - Cosmic Rays
問題概要：(xs,ys)から(xg,yg)への最短経路長問題
ただしN個の点(xi,yi)の半径ri内は距離をカウントしない
制約：
- −109≤xs,ys,xt,yt≤109
- (xs,ys) ≠ (xt,yt)
- 1≤N≤1,000
- −109≤xi,yi≤109
- 1≤ri≤109
任意のバリア2点間を移動することを考える。(xi,yi)から(xj,yj)へ移動するときの経路長が最も短くなるのは直線で移動するときなので、スタートとゴールをr=0のバリアと考え、各バリア間に重さmax(0,
)の辺を張ってdijkstraをするとスタートからゴールまでの最短経路長が得られる。
隣接行列を使ってdijkstraで解くと計算量はO(N^2)
