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