### PROBLEM LINK:

**Author:** Nibir Pal

**Tester:** Soumyadeep Roy

**Editorialist:** Soumik Sarkar

### DIFFICULTY:

Hard

### PREREQUISITES:

Graph theory, Dijkstra’s shortest path algorithm

### PROBLEM:

Given a weighted bi-directional graph, the task is to find out the shortest path length when **at most** a single edge is removed, the identity of which is provided by a query. Multiple such queries are made.

### EXPLANATION:

### Approach 1:

The simplest approach is to run Dijkstra’s algorithm for each query by removing the edge as directed, but this is not fast enough.

### Optimised Solution:

We observe that unless an edge is removed which lies on **ALL shortest paths** from the source to the destination, the answer is simply the shortest distance from source to destination. Let us call such an critical edge a **bridge**.

Further, let us call an edge **OPTIMAL** if it lies on ANY shortest path from source to destination.

Clearly, all bridges are optimal edges. We can sort these bridges by increasing order of their distances from the source. Then we can number them by their indices, starting from **0**.

Now, let us define an **island i** as a collection of vertices that can be reached by crossing all bridges numbered **0** to **i-1** and no more, by using only the shortest path tree of our given graph with the source as **root**.

In case a bridge i is removed, the shortest path must utilize an edge that links any island numbered **0** to **i** with any island numbered greater than **i**.

Let us define: **bypass(i)** as the required answer when bridge **i** is removed.

Now, to determine all such bypass values, we can iterate over every edge that connects two islands **i1** and **i2** (clearly no optimal edge fulfils this criteria) and for every bridge **i** in **i1** to **i2-1** we set **bypass(i)** to the shortest path distace utilizing this edge if it is found **less than** the current value of **bypass(i)**.

However, this results in an **O(E^2)** algorithm, and we can do better.

We can use any range update and query structure like **segment tree** to update the range **i1** to **i2-1** as required, and then query a particular **i** when required, both in **log n** time.

Now we can develop an algorithm.

First we run **Dijkstra’s algorithm**, once from destination and once from source. We store the paths traversed when run from source. This is required for future steps.

**Find all bridges:**

Consider an edge e joining vertices **u** and **v**. Now if distance between source and **u** + weight of **e** + distance between destination and **v** = shortest path distance between source and destination, edge e is optimal. We can then determine all the optimal vertices. Now we know that each bridge lies on all shortest paths from source to destination, thus an optimal edge at a unique distance from the source and destination must be a bridge. Thus we can sort the list of optimal edges and find out the bridges.

**Identifying islands:**

To identify islands, first we construct the shortest path tree. Now we can simply traverse this tree, and assign an island number to each vertex by counting the number of bridges crossed to get to that vertex.

**Getting bypass values:**

Iterate over all non-optimal edges. For each such edge e connecting island **i1** and **i2**, range update **bypass(i)** for all **i** in **i1** to **i2-1** as required using a preferred data structure.

Now it’s a simple matter to answer queries. If the removed edge is bridge **i**, query the data structure with **i** and print the value, else simply print the shortest path distane between source and destination

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.