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 obviously 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. Henceforth, 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 a little 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?
