1700. The Route When One Road Is Closed

An undirected graph has n vertices and m edges numbered 1 to m in input order, every weight at least 1. Then q questions arrive, each a single edge number. For each question, print the smallest total weight of a route from vertex 1 to vertex n when THAT edge is closed, or -1 if there is no such route.

Each question is independent: the edge is closed for that question only.

``` 4 vertices 1: 1 - 2 (1) 2: 2 - 4 (1) 3: 1 - 3 (1) 4: 3 - 4 (1)

close edge 1 -> 2 the other side of the diamond still works close edge 3 -> 2 ```

## The four things that have to be said

directed? no. Every edge may be walked either way, and closing it closes both directions. self-loops? allowed, and closing one changes nothing, since it is never on a cheapest route. parallel edges? allowed and important: closing ONE copy of a pair leaves the other open, so the answer may be unchanged or may jump to the dearer copy. Closing by NUMBER rather than by endpoints is what makes that expressible. unreachable? yes, per question. Closing a bridge can disconnect the graph, and then that question prints -1 while the others still get numbers. When n is 1 the answer is 0 for every question, since the empty route uses no edge.

## What most people try first

Finding the cheapest route once and answering every question from it: if the closed edge is not on that route, print the original distance, otherwise recompute. The first half is wrong and the second is right.

The first half fails because the ONE route found is not the only cheapest route. On the diamond above, closing edge 1 removes an edge that is on the route the search happened to pick, but the answer is still 2 because the other side of the diamond costs the same. So "on the route" is the wrong test.

The test that IS valid is whether the edge lies on ANY cheapest route, which problem 1670 shows how to decide with two searches: edge (u, v, w) can be on a cheapest route exactly when ds[u] + w + dt[v] or ds[v] + w + dt[u] equals ds[n]. An edge failing that test cannot affect the answer, so the original distance is correct for it.

## The method

run the search once to get ds from vertex 1 and dt from vertex n for each question, edge e = (u, v, w): if ds[u] + w + dt[v] != ds[n] and ds[v] + w + dt[u] != ds[n]: print ds[n] the edge is on no cheapest route else: rerun the search with edge e removed and print the result

With q at only 50, rerunning is O(q * m log n), about 50 * 50000 * 15 = 4 * 10^7 operations, which is why the cheap test is an optimisation rather than a necessity. It is worth having because it is the step that generalises: at q = m the reruns would dominate and only the edges on the shortest-path structure would be left to do.

## Why closing an edge can only make the answer larger or equal

Removing an edge removes routes and adds none, so the set of available route totals shrinks and its minimum cannot fall. That is the sanity check to assert while testing: every printed number is at least ds[n], or -1.

It also means a question can never print a number smaller than the unrestricted answer, which catches the most common implementation error at once: forgetting to RESTORE the edge before the next question, which closes edges cumulatively and makes later answers too large rather than too small.

## Overflow, computed rather than assumed

A cheapest route is simple, so it uses at most n - 1 = 19999 edges of up to 10^9, about 2 * 10^13, past the 2147483647 a signed 32 bit integer holds, so the distances need 64 bits. The three-term sum ds[u] + w + dt[v] reaches about 4 * 10^13, still far inside a signed 64 bit integer, but an INFINITE marker must not be added to another: test both distances for finiteness before forming that sum.

## Cost

O(m log n) for the two initial searches plus O(q * m log n) for the reruns, and O(n + m) memory. The cheap test removes most questions from the second term in practice.

Constraints - `1 ≤ n ≤ 20000` - `1 ≤ m ≤ 50000` - `1 ≤ q ≤ 50` - `1 ≤ u, v ≤ n` - `1 ≤ w ≤ 1000000000` - Each question names an edge number from 1 to `m`.