読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

0-1 BFS

0-1BFS

0-1BFS の紹介です。といいつつ、昨日のCFで出題された問題を別の実装で通したものを貼っているだけです。

pekempey.hatenablog.com

解法

0-1 BFS をすることにより縮約は不要になる。0-1 BFS というのは辺のコストが0か1のときの単一始点最短経路を求めるアルゴリズムである。 BFS ではqueueを使っていたが、これをdequeに変える。コスト0の辺をたどるときは deque の先頭に push し、コスト1の辺をたどるときは deque の末尾に push するようにすると正しく最短経路が求められる。

この問題は木なのでBFSやDFSで処理できるが、このアルゴリズムであれば一般のグラフでも正しく最短路を求められる。