2 ms·
In this particular problem, all edge weights are 1..=9, so you can have a O(1) priority queue (fixed-bound bucket queue) if you make use of that fact. (example
by aldanor 5y ago
In this particular problem, all edge weights are 1..=9, so you can have a O(1) priority queue (fixed-bound bucket queue) if you make use of that fact.
(example: https://github.com/aldanor/aoc-2021/blob/master/src/day15/mod.rs https://github.com/aldanor/aoc-2021/blob/master/src/day15/mo...)
- furstenheim 5y agoActually you don't even need a priority queue. Two lists, you read from one push to the second. When you are done you swap them