### PROBLEM LINK:

**Author:** Sergey Kulik

**Tester:** Vlad Mosko

**Editorialist:** Pushkar Mishra

### DIFFICULTY:

Medium

### PREREQUISITES:

Dijkstra’s Algorithm, Floyd Warshall, All Pairs Shortest Path Problem

### PROBLEM:

Given is a graph G with N nodes and weighted edges. Out of these N nodes, K are special nodes. We are required to find the minimum distance between any two special nodes.

### EXPLANATION:

**Subtask 1**

In this subtask N \leq 300. This implies that we can simply perform the floyd-warshall algorithm for finding the shortest distance between all pairs of nodes. Once we have prepared the table of such distances all we need to do is iterate over all pairs of nodes and take the minimum of all distances between the special nodes. Floyd-warshall algorithm is \mathcal{O}(N^3). This complexity is fine for this subtask.

**Subtask 2**

For this subtask N \leq 10^5. Since, graph is connected, there are at least as many edges. Clearly, we can’t apply the algorithm used in the first subtask since it will exceed time limit. The problem asks us the shortest distance between any two special nodes in the graph. This leads us to an observation. We only need to think about distances of nodes from the special nodes. In other words, we do not need the “all pairs shortest path” algorithms. We just need the shortest distance from the special nodes to all the nodes in the graph. For this subtask, the number of special nodes is less than or equal to 10. That is a fairly small number. All we have to do is run Dijkstra’s algorithm from each of the special nodes. This will give us the shortest distance of each node from the special nodes. We can then find the shortest distance between any two special nodes. The complexity of dijkstra’s algorithm is \mathcal{O}(N\log N). Therefore, the complexity of this algorithm works out to be \mathcal{O}(NK\log N). This is sufficient for this subtask.

**Subtask 3**

In this subtask, the number of special nodes increases to 10^4. We can’t get the previous algorithm to work under the given time limits.

Let us start by thinking of an algorithm to solve a simpler version of the given problem wherein all edges are of weight 1. Now we propose the formal algorithm for this problem and then prove its time complexity.

The formal algorithm is as follows:

- We pick a random special node and perform a BFS from this point. We stop at the first level s which contains another special node.
- We know that the minimum distance between any two special nodes can’t be more than s. So we again take a special node at random which hasn’t been taken before and perform a BFS again. If we don’t find any special node in s distance, we terminate the search. If we do, then we update the value of s and repeat the procedure with some other special node taken at random.

It is pretty intuitive why this algorithm gives the correct answer. But why does it run within the given time limits? What is its time complexity?

In the first look the algorithm seems to have a complexity of \mathcal{O}(NK). But in fact it is \mathcal{O}(N\log N). Basically, we show that after each iteration of the BFS, the minimum distance to be searched before which another special node is found – henceforth referred to as the radius of search – becomes half. Let us see why.

After the first run of BFS from the randomly chosen special node, we can have two cases:

- s \geq \frac{N}{2}
- s < \frac{N}{2}

In the second case, we can clearly see that the search radius for the next BFS will be \frac{N}{2}, i.e., half of the current one. This is because we will anyway terminate the search if we don’t find a special node in that radius. But what happens in the second case?

If s \geq \frac{N}{2}, this means that all the other special nodes apart from the one we started our BFS on must all be clustered within a radius of N-s. Since s \geq \frac{N}{2}, this means that in the next BFS, we will definitely find a special within \frac{N}{2} radius of the one we start on.

Therefore, we see that in every iteration of BFS, we half our search radius of the graph. The algorithm therefore is \mathcal{O}(N\log N).

We can now go back to our original problem. Since, our original problem involves edges of different weights, instead of performing BFS, we need to perform Dijkstra’s algorithm. But how many times? Following the same reasoning as the simpler version of the problem, we get that Dijkstra will be performed \mathcal{O}(\log S_e) times, where S_e is the sum of weights of all edges in the graph. This gives a total runtime of \mathcal{O}(N\log N\log S_e) which is sufficient for the given constraints.

Editorialist’s program follows the editorial. Please see for implementation details.

### OPTIMAL COMPLEXITY:

\mathcal{O}(N\log N\log S_e) where S_e is the sum of weights of edges.