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

ツリーグラフにおける最短ルートの算出

グラフ理論 最短距離 木構造 AtCoder

問題

B: ツリーグラフ - AtCoder Regular Contest 030 | AtCoder

解法

与えられたノードからスタートし、宝石を全て取得するように巡回し始めのノードに戻ってくるルートの最短距離を求める問題。 それぞれのノードについて、巡回すべきノードであるか否かを判定し、巡回すべきノードであれば距離を加算していく。

深さ優先探索を使う。親ノード以外進むノードがなくなった時に、そのノードに宝石があるか否かをチャック。宝石がある場合はそのノードは必ず巡回する必要があるので往復分の2を加える。宝石が無い場合は巡回しないので、そこを巡回する分の距離は加えない。

ソースコード