12/21 競プロ典型003
グラフの最短距離の最大値
考え方
ある頂点aから一番遠い頂点bを探す
その頂点bから一番遠い頂点cが最短距離の最大値
テクニック
ある頂点から移動可能な頂点をひとまずキューに入れる
その頂点までの距離は、今まで辿った距離＋1
同じ深さの頂点をキューに追加していって、キューが空になるまで繰り返し
考え方はわかる
幅優先や深さ優先の実装が出来ないよう
その頂点に行ったことがあるかをtrue,falseでやるのも良いが、距離をINFにしといて距離まで同時に考えるのもスマート
書き方
二次元配列
キュー
queue<型> Q
Q.push(a);キューにaを追加
Q.empty();キューが空ならtrue
Q.front();キューの先頭を参照
Q.pop();キューの先頭を削除
