幅優先探索の一般的な罠この広告は、90日以上更新していないブログに表示しています。幅優先探索でTLEする一般的な罠の解説です。いうグリッドを幅優先する問題で起こりやすいですね。AtCoder簡単のためこのような迷路を考えます。endl;queの中身がこうなってしまいます。{(b,6)}->{(b,5),(c,6)}->{(c,5),(c,5)}//ん?->{(c,4),(d,5),(c,4),(d,5)}->{(d,4),(d,4),(d,4),(d,4)}->{(e,4),(d,3),(e,4),(d,3),(e,4),(d,3),(e,4),(d,3)}//あれ?このように指数的に増えていってしまうので、TLEしてしまいます。・(b,5)を見ているとき、(c,5)はまだ行ったことが無いのでqueに追加します・(c,6)を見ているとき、(c,5)はまだ行ったことが無いのでqueに追加しますという動作になってしまっているからです。これを解消するには、同じものを二回以上見ないように、「そこはもう調べることになっている」という段階で枝狩りしてやります。endl;visitedに代入するタイミングを変えただけですね。Bの道(コスト101333)を通りたく無い。部内での共有用に久々に書いてみようと思います。問題のURLはこちらです。eiya5498513リンクはてなブログブログをはじめる週刊はてなブログはてなブログPro参加グループプログラミングはてなブログをはじめよう!eiya5498513さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。