Maybe in year or two.

Forum is not for instant answers. It is rather knowledge base. There is no answer to your question in the base yet.

Maybe answer will appear but 99% that _you_ will first find the bug and post yourself test for the bug here than someone get wa29 and post test for it.

I tried it this way - i.e. propagate all with 1, then with sqrt(2) from current frontier to upcoming edges, but here is the thing:

distance 0 leads to 1 and 1.4 (all still fine and sorted)
distance 1 leads to 2 and 2.4 (all still fine and sorted)
distance 1.4 leads to 2.4 and 2.8 (all still fine and sorted)
distance 2 leads to 3 and 3.4 (all still fine and sorted)
distance 2.4 leads to 3.4 and 3.8 (all still fine and sorted)
distance 2.8 leads to 3.0 and 4.2 (WOOPS! - 3.0 will be placed after 3.4 and 3.8)

so I did  Dijkstra, but with super-optimization. Instead keeping all nodes in a heap, I kept a heap on unique distances (as of A+B*sqrt(2)), and for each such distance I kept bidirectional list of nodes with that distance as currently reached. This makes edge relaxation O(1) - remove from current list, and add to another. So it's O(N*M)+O(K*log(K)) where K is number of different distances, and there are not so much on the way. Although I checked with asserts, there are cases when you have like 8 or even 16 upcoming frontiers even during first 6 tests. Relexations start happening with test 5, but only test 7 leads to WA on them with too greedy approach.

Edited by author 24.06.2026 11:43

Because you can't get three trips here no matter the ordering