C: Blue Bird - AtCoder Beginner Contest 022 | AtCoder
1 から出て 1 に戻る道を考えるが,まず,1に隣接している点から出て別の隣接している点に戻る道を考える.
1を除いたグラフについてワーシャルフロイドで全組み合わせの最短距離を求めておく.
1に隣接している点から2つずつ選び,点1 - 点i,点i-点j,点j-点1 の和の最小値を求め,答えとする.
答えがグラフを初期化した値より小さくなっていなかったら -1を出力.
C: Blue Bird - AtCoder Beginner Contest 022 | AtCoder
1 から出て 1 に戻る道を考えるが,まず,1に隣接している点から出て別の隣接している点に戻る道を考える.
1を除いたグラフについてワーシャルフロイドで全組み合わせの最短距離を求めておく.
1に隣接している点から2つずつ選び,点1 - 点i,点i-点j,点j-点1 の和の最小値を求め,答えとする.
答えがグラフを初期化した値より小さくなっていなかったら -1を出力.