ダイクストラと非負整数辺BFSなどめっちゃ色々試した TopCoder SRM 612 Div1 Easy EmoticonsDiv1
みんなやさしい。ありがとうございます。
@ryo_wk https://t.co/DuGkFZernY こういう事だと思います（適当に書いたのでどっかバグってるかも）。 01-bfs のように差分だけを持つパターンも https://t.co/qPVbeuzkgE
— koyumeishi (@koyumeishi_) 2017年2月15日
@ryo_wk 再計算が必要なやつはDPとは呼ぶイメージはないですね。一般的には全点再計算の可能性があるので計算量はn倍くらいされる(=ダイクストラより遅い)と思います(あまり自信ないです)。
— まっつん (@y_mazun) 2017年2月15日
@ryo_wk 辺の重みが0か1の場合、priority_queueの代わりにdequeを使うとlogが落ちます（0なら先頭に追加・1なら末尾に追加）。同じように重みが小さい範囲にあるならqueueをたくさん用意するとlogが落ちます。
— not (@not_522) 2017年2月15日
@ryo_wk 01BFSみたいなやつです
— not (@not_522) 2017年2月15日
@ryo_wk 競プロ界隈では区別のためにメモ化再帰と呼ぶことが多い印象ありますね。DPと呼ぶことは問題ないと思いますが
— まっつん (@y_mazun) 2017年2月15日
