dijkstraの空間計算量(メモリ使用量)をO(V)に減らす
Priority Queue を使った実装だと時間計算量 \(O(V + ElogE)\), 空間計算量 \(O(V + E)\) になると思います。
実装は重くなるのと定数が重いですが、Priority Queue の代わりに Segment Tree を使うと時間計算量 \(O(V + ElogV)\), 空間計算量 \(O(V)\) に改善できます。
これを使うと楽に解ける問題
RUPC2019 Day2 E こたつがめを燃やさないで
https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day2/problems/E