cheran-senthil / PyRival

⚡ Competitive Programming Library
https://pyrival.readthedocs.io/
Apache License 2.0
1.17k stars 312 forks source link

Switching to segtree based Dijkstra for extra speed #55

Open bjorn-martinsson opened 3 years ago

bjorn-martinsson commented 3 years ago

Python has a problem with being slow when it comes to having tuples inside of a heap. There have been multiple problems on codeforces.com with currently no accepted python heap Dijkstra solutions. This PR adds a much more optimized Dijkstra using segment trees to get around using tuples and heaps.