AOJ 1169 : The Most Powerful Spell ( 最強の呪文 )

グラフ 文字列

The Most Powerful Spell | Aizu Online Judge

問題概要

  • 始点と終点のある有向グラフが与えられます。
  • 各エッジには文字列を持ちます。
  • 始点から終点まで辿った時にできる連結した文字列の辞書順最小を求めて下さい。
  • ただし、文字列を無限に最小にできる場合とそもそも終点に辿りつけない場合は"NO"を出力してください。

解法

  • dijk[ 今いる頂点 ][ 今何文字か ] = 現在の文字列
  • 現在の文字数が等しければある頂点にいる時の最適な文字列は一意に定まる。（これ重要）
  • 辺の数は400で辺の持つ文字列の長さ6以下らしいので最大でも240字程度なので300文字以上の終点にたどり着くより辞書順で小さい文字があったら"NO"
  • そもそも終点に答えが無ければ"NO"
ソースコード

感想

いや、難しくない？

頂点と現在の最適な文字列だけで見るとコーナーケースがたくさんあるので、文字数を見ることが大事！！！