2019-03-09から1日間の記事一覧

dijkstraの空間計算量(メモリ使用量)をO(V)に減らす

Priority Queue を使った実装だと時間計算量 \(O(V + ElogE)\), 空間計算量 \(O(V + E)\) になると思います。実装は重くなるのと定数が重いですが、Priority Queue の代わりに Segment Tree を使うと時間計算量 \(O(V + ElogV)\), 空間計算量 \(O(V)\) に改…