Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Try reusing arrays in "mincostflow" #29

Open
kenkoooo opened this issue Sep 10, 2020 · 1 comment
Open

Try reusing arrays in "mincostflow" #29

kenkoooo opened this issue Sep 10, 2020 · 1 comment

Comments

@kenkoooo
Copy link
Contributor

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 #25 (comment)

@MiSawa
Copy link
Contributor

MiSawa commented Sep 11, 2020

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.

@qryxip qryxip pinned this issue Sep 23, 2020
@qryxip qryxip unpinned this issue Apr 9, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants