ABC292 E - Transitivity (500)
愚直に実装すると、3点間の組み合わせを全部見る必要があるので
$ \mathcal{O}(N^3)
最終的にどういう形になるかを考えると、初期の状態で到達可能かつ距離が2以上の点全てに辺を追加することになる
なので各点からBFSで各点への最短距離を求め、距離2以上のものの数を操作回数に足していく
問題:
https://atcoder.jp/contests/abc292/tasks/abc292_e
提出:
https://atcoder.jp/contests/abc292/submissions/39424614
#ABC292
#500pt
#E
#ABC
#AtCoder
#BFS
#O(N^2)