My 2021 day 23 runs in 5 milliseconds for both parts using A* with a custom heuristic: https://github.com/orlp/aoc2021/blob/master/src/bin/day23.rs