JOI国の買い物事情(11本選3)
N個の町、M本の道、K個のショッピングモールがある。
ショッピングモールは町の中にある。
町及び道の中で一番近いショッピングモールまでの距離が最大の値を求める問題。
まず、dijkstraで町までの距離を求め、各辺について辺上で一番遠い点を求める。
計算量はO(NlogN)
難易度は5程度に感じられた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2325415#1
N個の町、M本の道、K個のショッピングモールがある。
ショッピングモールは町の中にある。
町及び道の中で一番近いショッピングモールまでの距離が最大の値を求める問題。
まず、dijkstraで町までの距離を求め、各辺について辺上で一番遠い点を求める。
計算量はO(NlogN)
難易度は5程度に感じられた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2325415#1