競技プログラミング用 知識集積所
ABC451E - Tree Distance
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
長い辺で短い辺を代用することができない以上、答えがあるとしたら最小全域木※になっているはず。
よって、距離条件に違反していないかチェックしながらそれを構成するだけ。
クラスカル法は複数の連結成分がつながるときに距離のチェックが少し面倒くさい。
プリム法なら毎回1点をつなげるだけなので、「付け足す点→根本→目的地」が「付け足す点→根本」「根本→目的地」の和に一致するか、すでに連結済の全目的地に対してチェックするだけなので簡単。
よって、距離条件に違反していないかチェックしながらそれを構成するだけ。
クラスカル法は複数の連結成分がつながるときに距離のチェックが少し面倒くさい。
プリム法なら毎回1点をつなげるだけなので、「付け足す点→根本→目的地」が「付け足す点→根本」「根本→目的地」の和に一致するか、すでに連結済の全目的地に対してチェックするだけなので簡単。
