No.022 C

頂点 $1$ を含む最小の閉路を求める問題である.

頂点 $1$ を含む閉路なので, 頂点 $1$ につながっている2つの頂点を通る. この2頂点を $i, j$ とすると, 頂点 $1$ を含まないグラフでの頂点 $i, j$ 間の最短距離と頂点 $1, i$ 間の距離と頂点 $1, j$ 間の距離の最小値が最小の閉路の距離となる.

頂点 $1$ を含まないグラフのすべての頂点間の距離を Floyd Warshal 法で求めておき, 上記頂点 $i, j$ のすべてのパターンで計算する.