Graphs, shortest paths, binary search, Bellman-Ford algorithm
For a given nodes A and B, find the average length of a walk between A and B that has the smallest average length among all such walks or decide that there is no walk between these nodes.
First, check if B is reachable from A. If not, we are done. Otherwise, perform a binary search over all possible resulting average lengths. For a fixed average length L, use Bellman-Ford algorithm to find out if the graph has a walk from A to B with average length less or equal to L.
In the first subtask the constraints are very small, we have at most 10 vertices and at most 20 edges. One may try various approach within these constrains. One of them may be to first find out average lengths of all simple paths from A to B by examining all of them, and after that, try to form an infinite walk between A and B by adding a cycle with some minimum length L, which when the walk is infinite, will dominate other length is such a path. Alternatively, some approximate solutions may be also possible, because the required precision of the answer in this subtask is not very restrictive.
Let’s assume that B is reachable from A, because in the other case the answer is obvious, and this can be easily check by a simple DFS. After that, let’s try to solve a different problem:
For a given value L, decide if there exists a walk from A to B with average length not greater than L.
How is this problem simpler than the original one? Well, let’s assume that there exists a walk W from A to B with average length less or equal to L. Now, let’s subtract L from all weights of edges in the graph. How does this operation affect W? Since its average length was not greater than L before, and we subtracted L from all weights, now its absolute length is not greater than 0. Moreover, this operation of lowering weights of edges affects all paths in the same way, i.e. the relative order of their average lengths is not affected by the operation (be careful here, this is not true when operating on absolute lengths instead of average lengths).
So far so good, but how to find out if there is a walk from A to B of length not greater than 0? It is very important that we are looking for a walk, not only for a simple path here. Moreover, after subtraction, weights on edges can be negative, which is also important for certain algorithms to work. Fortunately, Bellman-Ford algorithm can be used here. It works perfectly with negative edges and can be used to detect if a graph has a negative length cycle, which is crucial in the solution.
In order to find out if there is a walk from A to B with length not greater than 0, we run Bellman-Ford algorithm to compute the shortest simple path from A to B. If its length is not greater than 0, we are done. Otherwise, we use Bellman-Ford to check if there is a negative length cycle C in the graph, with the property that C is reachable from A and B is reachable from C. If there is any such cycle C, then by traversing it enough number of times, we can always lower the cost of the path (which is in fact a walk right now) to be not greater than 0. If there is no such cycle, then there is no walk from A to B with length not greater than 0, because there is no such simple path between them with that property and there is no negative cycle which can lower a cost of any path from A to B. This solution works in O(N * M) time, because this is the running time of Bellman-Ford algorithm. Thus in this time we can solve the problem of deciding for a fixed value L if the graph has a walk from A to B with average length not greater than L. How to use this fact to solve the original problem? Well, we can use binary search over all possible values of L, and for a fixed value of L we can solve the problem described above. Notice that since all weights of edges in the graph are within a range [1, 100], all possible values of L are also within this range. Moreover, since the required precision of the answer is to return it with absolute or relative error not greater than 10-6, we can stop binary search as soon as the range of valid values of L is reduced enough to fulfill this requirement. For more details please refer to author’s and tester’s solutions.