以下の内容はhttps://jupiro.hatenablog.com/entry/2020/09/18/210923より取得しました。

解説

最短経路木を列挙してくださいという問題です。

頂点1からBFSなどで各頂点までの最短経路 $d$ を求めましょう。

ある頂点 $t$ の親 $p$ は $d _ {p} + 1 == d _ {t}$ となるものに限り、かつこれを満たすならどれでも構わないです。

あとはこのパターンを列挙するだけで、列挙の仕方はfor文を回したりBFSなどいろいろあると思います

計算量は $O(n + mk)$ です

提出コード

以上の内容はhttps://jupiro.hatenablog.com/entry/2020/09/18/210923より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます

不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14