ARC(AtCoder Regular Contest) 030 C - 有向グラフ

C: 有向グラフ - AtCoder Regular Contest 030 | AtCoder

[問題]

n個の頂点とm本の辺の有向グラフがある。各頂点には'a'-'z'のアルファベットが１個ある。任意の頂点から開始してグラフをたどり、アルファベットを合計k個順番に取る。各頂点では取っても取らなくてもいい。循環していれば一回スキップして後で取ってもいい。取得した文字列の辞書順最小を求める。存在しなければ-1を返す。

[解答]

(終了後)

強連結成分分解でループしているところをグループ化する。各グループの文字はどの順番でも取れるのでソートしておく。

グループを順にたどり、文字数ごとに、それまでに作成できた最小の文字を記録する。

(DP[グループ][文字数]で最小の文字列を記録)

[コード](C++)

https://paiza.io/projects/icf5SNr67K43_VO65QhPzg

[感想]

O((N+M)*N*K*26)かな。他の人の解答や解説を見ながらだけど、はじめての強連結成分分解。少し慣れないと競技中には難しそう。DPの初期値文字列は"~"とする方法もありそう。