読者です 読者をやめる 読者になる 読者になる

olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

JOI国の買い物事情(11本選3)

N個の町、M本の道、K個のショッピングモールがある。

ショッピングモールは町の中にある。

町及び道の中で一番近いショッピングモールまでの距離が最大の値を求める問題。

まず、dijkstraで町までの距離を求め、各辺について辺上で一番遠い点を求める。

計算量はO(NlogN)

難易度は5程度に感じられた。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2325415#1