ac-library-rs
ac-library-rs copied to clipboard
Try reusing arrays in "mincostflow"
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
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.