Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2008-10-19

CavePassage (SRM422 DIV1 Medium)

| 00:29 | CavePassage (SRM422 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - CavePassage (SRM422 DIV1 Medium) - TopCoder煮ブログ

解けている人の解法を見ると、次の方針でやっているようだ。

  • 2^N と行ったとき帰ったときの2通りの状態(=16384通り)がある。
  • それぞれを移りながらダイクストラ法で解いていく。
    • 16384^2 の状態をグラフとして持つのは大変なので、ノード一覧だけ保持して計算していく。
    • ダイクストラ法はメモリ量が少ない!!

C++ 一位の人のソースを理解したあとで暗証してみた。細かい部分がより分かるようになった。priority_queue を使わない方法も試してみて、ダイクストラ法への理解が深まった気がする。