ABC 016 C - 友達の友達

atcoder.jp

kenkoooo.comのdifficulty同じ数値でも最近の問題と昔の問題で難易度に差があるように感じるんだけど、こんなもんなんですかね

初手の方針

まだ知識がないので少ない中で知っている知識に帰着させようとしてUnionFindで実装しようとした。 が、繋がっている全員が対象ではなく距離でいうと自分から2離れたところまでしか対象にならないなと思い重み付きUnionFindなど調べ始めた。結局友達のリストを愚直に数え上げても全然間に合うということでそういう実装にした。

Submission #11964386 - AtCoder Beginner Contest 016

正答

一応上の方法でも間違いではないが、関連をグラフとして捉えて自分から距離2の地点の相手を見つける問題と捉えるのが筋が良さそう。 解答だとダイクストラ法、ワーシャルフロイド法などで解くことができるとあったので今回は基礎的（に見えた）ダイクストラ法で解くことにした。

Submission #12044579 - AtCoder Beginner Contest 016

振り返り

ダイクストラ法

コストが非負の最短経路問題を解くためのアルゴリズム、現在のノードから次のノードのコストが決まるという意味でDP的な手法と言える。エッジに重みがある場合の最短経路を解くことが可能(今回の例では全てのエッジのコストが1なので幅優先探索でも解ける)

1. 現時点から繋がるノードをpriority_queueに積みコストと訪問済みフラグを更新する
2. もっともコストの低いノードを取り出す(移動する)
3. 移動したノードに対して1の作業を行う

以下繰り返し

- アルゴリズムについてはヨビノリさんの動画がわかりやすい

www.youtube.com

- 実装についてはこちらの記事

ダイクストラ法（最短経路問題）

structとqueue

structに対してqueueを利用するにはoperator<のoverloadが必要. またoperatorでprivate変数を参照する場合はfriendをつける.

一般的には、いったん operator< が提供されれば、他の関係演算子は operator< を用いて実装されます。

演算子オーバーロード - cppreference.com

struct Node {
  vector<ll> edges;
  vector<ll> costs;
  bool done;
  ll cost;
 
  friend bool operator<(const Node& lhs, const Node& rhs){ return rhs.cost < lhs.cost; }
};