ABC021 C - 正直者の高橋くん

C - 正直者の高橋くんを解いたので雑に解法のメモを書きます。

問題

C - 正直者の高橋くん

考察

グラフの最短経路数を求める問題。

グラフの最短距離を求めるという典型問題と、経路の数を求めるという典型問題がくっついた感じ。

1. aから各点への最短距離を求める
2. 各点への最短経路数を順番に数えていく

という方針で解いた。

最短距離は、BFS（と、簡単なDP）で簡単に求まる。

頂点を複数回たどらないように注意しつつBFSしていけば自ずと最短距離になるので、始点aを0として、次の頂点に進むときに現在の頂点への最短距離 + 1 しながら探索していけばよい。

次に、最短経路数をどうやって求めるか。

これは配るDP的なイメージで、ある頂点の最短経路数をそこから進むことができる隣接する頂点に配っていけばよい。

始点aからaへの最短経路数は自明に1とわかるので、そこから順番にbまでBFSしていけば求まる。

ただし探索済みの頂点であっても最短距離なら進むことができるので、探索済みだからといって無視せずに最短距離なら経路数を配るようにする必要があることに注意。

ちなみに二回BFSする必要はなく、距離と経路数の更新を同時にやればよい。

自分の提出

グラフの入力だけ 0 indexed に直してaとbだけ直し忘れたりしたので、0 indexed 派な場合はそこら辺のうっかりミスに要注意・・・かも😅。