怠惰の累積和

技術/競プロ/怪文書/虚無

AtCoder Beginner Contest 016 C - 友達の友達

問題概要

M個の友達関係が与えられるので各人に対して「友達の友達」の人数を出力する。

atcoder.jp

解法

「友達の友達」の人数であって、友達の人数は含まないことに注意。自分は友達関係をグラフに持って、dijkstraで各人の頂点からの最短距離を求めることにより、その人からの最短距離が2なら(最短距離が1で友達の関係なので)友達の友達の人数を追加する方式で実装した。

atcoder.jp