AOJ 1169 : 最強の呪文 (The Most Powerful Spell)
接頭辞の長さごとに、辞書順最小となるものを求めるようなダイクストラ法。ゴールへの経路は、もし閉路を含まなければN個以下の頂点からなるはずで、接頭辞の長さの最大値は6*(N-1)
これより長い接頭辞で、辞書順がさらに小さいような経路があれば、その呪文は閉路を含んでいるはずであり、辞書順がより小さい呪文を作れるのでNOを出力。そもそも経路がない場合も。
そうでなければ辞書順最小の呪文を出力。
接頭辞の長さごとに、辞書順最小となるものを求めるようなダイクストラ法。ゴールへの経路は、もし閉路を含まなければN個以下の頂点からなるはずで、接頭辞の長さの最大値は6*(N-1)
これより長い接頭辞で、辞書順がさらに小さいような経路があれば、その呪文は閉路を含んでいるはずであり、辞書順がより小さい呪文を作れるのでNOを出力。そもそも経路がない場合も。
そうでなければ辞書順最小の呪文を出力。