WUPC 2012 E - 会場への道

• 問題
• AC

いったん会場に着いたら戻れないというルールを見落としてWAし続けた。コーナーケースで落ちてるっぽい時は、問題文を読みなおすべき。

あと、ダイクストラ法の空間計算量の見積もりをときどき間違えてしまう。ダイクストラ法では１つの辺につき高々１回しかenqueueされないので長さ$|E|$の優先度付きキューを用意すればよいのだが、今回は28倍に増えるので$28 \times |E|$……ではなく、逆辺もあるので$28 \times 2 \times |E|$だった。¹ （追記） 結局二分ヒープを可変長にしたらこの手の悩みがなくなった。もっと早くやればよかった……

---

1. 一般の無向グラフでダイクストラ法をする場合、データとしては$2|E|$個の有向辺を持つことになるが、アルゴリズム中では辺$v \rightarrow w$がキューに加わる時点で頂点$v$への最短距離が確定しているので$w \rightarrow v$がキューに加わることはない。したがって、キューのサイズは$|E|$で十分である。ただ、この問題では頂点に状態を持たせた時点で無向グラフではなくなっている。 ↩︎