最長経路の中身を問うものではないので、12分でできても不思議じゃないけど。

広辞苑の中身が
あい
あいい
あうい
いあ
いいあ
の５個だったら、最後の単語が「あ＊い」であるということを見つけるのはそれほど
難しくない。