メモリ要求量 - Heap。

ダイクストラ法の探索候補点を保持するデータ構造に対して Heap を使うとかなりメモリ要求量を節約できる。

Heap 自体は、点 ID と Potential を保持しておけば済む話なので、それぞれ int なら sizeof(int) * n 程度。long long でも、sizeof(long long) * n ほどあれば十分である。

全米であるとそれぞれ 8byte * 24M = 192MB、16 byte * 24M = 384 MB ほどとなる。