search

rust-lang-ja / ac-library-rs

ac-library-rs is a rust port of AtCoder Library (ACL).
Creative Commons Zero v1.0 Universal
225 stars 27 forks source link

Try reusing arrays in "mincostflow" #29

Open kenkoooo opened 4 years ago

kenkoooo commented 4 years ago

In mincostflow, we can reuse some arrays.

It is said that using the distance component only in the compare function reduces the running time of dijkstra. I've never compared them by myself, but it might worth trying.

_Originally posted by @MiSawa in https://github.com/rust-lang-ja/ac-library-rs/pull/25#discussion_r485758288_

MiSawa commented 4 years ago

Actually reusing vector and priority queue instances would reduce the number of malloc and realloc, which might be important to do. Though my intention there was about the definition of comparison used in the priority queue. The original implementation uses this custom structure instead of pair<Cost, int> plus greater<pair<Cost, int>>, since in this way, we can avoid comparing the vertex ids in the comparison function.

I think we can create a helper wrapper struct like this, or create a struct in place like what the original impl do.