Hello,
so this article on USACO Guide explains an alternative way to implement a solution for the Manhattan MST problem, which is to run a modified Dijkstra algorithm that stores the distance to a node of the MST for each square of the grid. It starts at an arbitrary point in the input, and this point has a distance of zero to the MST. Then, a modified Dijkstra is run, with the difference being that whenever we encounter a square which is inside the input, we reset the distance of the square to the MST to zero.
However, this modified version of Dijkstra is not really the same as Dijkstra, because if a square is found that is part of the input, the distance to the MST gets reset to zero, and therefore, its neighboring squares get visited multiple times etc. Therefore, it's not possible to claim that this algorithm has the same running time as Dijkstra, because in Dijkstra, every node gets visited exactly once. However, the maximum number of times that a square can get visited is apparently 4 (I stress-tested the algorithm and that was the maximum number that I found). Could anyone explain the reasoning behind the 4 being the "magic upper bound" for the number of times that a square gets visited? Or could someone maybe prove me wrong and provide a sample where we visit some square at least five times?
After a discussion with sparsetable, I think I've finally figured it out.
Take a look at this image. The point $$$A$$$ is a point inside the input, while the point $$$B$$$ is not, and the square represents all points visited so far with $$$A$$$ as a source. Assume that to go from A to B, you need to go $$$n$$$ steps to the right and $$$m$$$ steps up. Also assume that $$$n > m$$$. That means that we went more steps to the right than we went up. This also means that more than half of the distance between $$$A$$$ and $$$B$$$ are spent with steps going right.
Take any point $$$C$$$ from the input where we would have to visit $$$B$$$ a second time. $$$C$$$ cannot be inside the square, because otherwise we wouldn't have to visit $$$B$$$ twice. $$$dist(A,B)>dist(C,B)$$$ must also hold true if we want to visit $$$B$$$ a second time. However, it is not possible that the path from $$$C$$$ to $$$B$$$ has more than $$$n$$$ steps to the right. So, point $$$A$$$ marks a maximum "right distance" of $$$n$$$. Since there exist 4 directions in which we can move (up, down, left, right), we can only visit a square at most 4 times.
based