AOJ 1169 - 最強の呪文
解法
それぞれの頂点にたどり着くときに文字数がになっているような呪文の中では、最強の文字列が常に一意に決まります。
ループをしない場合、文字数は最大でも240文字程度にしかなりません(頂点数が40、辺に与えられた文字列の長さは最長で6なので、全ての頂点を1度ずつ通るような遷移をしても234文字にしかなりません)。
ということで、
頂点
にいる状態で文字数が
文字となるような文字列のうち、辞書順最小のもの
とすると、これはダイクストラ法で求めることができます。
あとは、に格納されている文字列の中で辞書順最小のものを基本的に選べばよいです。
が、これだとループの判定ができません。
先ほど、ループをしない場合に文字数は最大でも240文字程度、ということがわかりました。つまり、それより多い文字数の文字列で、現状のにある文字列よりも辞書順で小さい文字列が存在していれば、それはループによって無限に呪文を強くできる、ということになります。1回のループにかかる文字数は先ほどと同様最大で240程度なので、その2倍の500文字程度を調べればよいです。
ということで、にある文字列の中で辞書順最小のものを調べ、その文字数が240を超えている(もしくはそもそも文字列が存在しない)ならば
NOを出力、そうでなければ辞書順最小の文字列が答えになります。
感想
一度頂点数そのままのダイクストラを考え無理だとあきらめた結果、辞書順最小になるということは、基本的に貪欲に辺を選んでいけばよいので、DFSを枝刈りしていけばいいのではないか、ということでだいぶ遠回りをしました。
よくよく考えると、頂点を増やしてグラフを拡張すればよいことに気づき、無事ACできました。高難度でもグラフ拡張系の割とシンプル(?)なダイクストラが出るのですね…
