The Most Powerful Spell | Aizu Online Judge
嘘解法くさいです。
ダイクストラに見えるけど違うのかな・・・?
と思ったらダメになるケースがある。
あらかじめ幅優先探索をして各ノードからゴールまでの最小文字列を求めておき、
これをヒューリスティックスコアとしてA*探索を行う。
ループが発生したら2400文字(ループさせないでまっすぐ行ったときに考えうる最大の長さ)まで
ループ部分を付け足しておき、最後にループさせないでゴールに着いた文字列と比較する。
としたらACできた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2355848#1
嘘解法くささ2
ループ判定。2度目にたどり着いて一定の条件を満たせばループ扱いになってしまう。
nが最大で40ぐらいだからbitで経由したノードを記録しておく必要がありそう。
嘘解法くささ3
そもそもこのアルゴリズムで正しい答えが出るのか・・・?
なんかすっきりしないACの仕方をしてしまった。
他のブログを参照するときちんと考察の上解いているので見習いたい。
少し背伸びをして難しい問題が解きたいと思って
700点でかつサークルの人たちが解いているこの問題に手を出してみた。
黄色ゾーンが埋まったらまた解きなおしたい。