The current implementation of Graph, especially Dijkstra, SPFA, and MCMF, is too slow and significantly affects the judge results. The primary issue lies in the adjacency list, which currently stores edge indices, requires additional time to access edge array and it leads poor cache locality.
Two possible improvements are below:
-
Manage two adj lists - one to store edge indices, and the other to store vertex numbers directly. It may consume a significant amount of memory.
-
Store only vertex adjacency lists and use edge information sparsely by utilizing sets or other similar structures. This approach can save memory and simplify the code. However, it may increase the time complexity when accessing edge information frequently.
The current implementation of Graph, especially Dijkstra, SPFA, and MCMF, is too slow and significantly affects the judge results. The primary issue lies in the adjacency list, which currently stores edge indices, requires additional time to access edge array and it leads poor cache locality.
Two possible improvements are below:
Manage two adj lists - one to store edge indices, and the other to store vertex numbers directly. It may consume a significant amount of memory.
Store only vertex adjacency lists and use edge information sparsely by utilizing sets or other similar structures. This approach can save memory and simplify the code. However, it may increase the time complexity when accessing edge information frequently.