1671. How Many Shortest Ways Are There

An undirected graph has n vertices and m edges, all of equal length. Print how many SHORTEST routes lead from vertex 1 to vertex n, reduced modulo 1000000007. Print 0 if there is no route at all.

A route is a sequence of edges, so two edges joining the same pair of vertices are two different routes.

4 vertices 1 - 2 2 - 4 1 - 3 3 - 4 -> 2

Both 1 - 2 - 4 and 1 - 3 - 4 use two edges, and no route is shorter.

## The four things that have to be said

directed? no. Every edge may be walked either way. self-loops? allowed, and never on a shortest route. parallel edges? allowed, and TWO COPIES ARE TWO ROUTES, since a route is a sequence of edges. unreachable? yes, and the answer is then 0 rather than -1, which is the honest count. When n is 1 the answer is 1: the route of no edges.

## What most people try first

Finding one shortest route, as problem 364 does, and then looking for others. There is nothing to look with: a breadth-first search that records a single parent per vertex has already discarded the alternatives as they arrived.

The second instinct is to enumerate the shortest routes and count them. The count can be exponential: a chain of k diamonds, each offering two equal sides, has 3k + 1 vertices and 2^k shortest routes. At k = 60 that is more routes than any machine will ever list, with 181 vertices. Counting is not a faster way to enumerate; it is a different algorithm.

## Carry the count beside the distance, and update it DURING relaxation

dist[1] = 0, ways[1] = 1, everything else dist = infinity, ways = 0 breadth-first search from vertex 1; on edge (u, v): if v has no distance yet: dist[v] = dist[u] + 1; ways[v] = ways[u] else if dist[v] == dist[u] + 1: ways[v] = ways[v] + ways[u]

The two branches are the whole problem. A strictly better distance RESETS the count, because every route found so far was longer and none of them is a shortest route any more. An equal distance ADDS, because the routes through u are new and distinct from the ones already counted.

## Why it cannot be done afterwards

The tempting repair is to run the search first and count later, by walking the tight edges. That does work, and it needs a second pass in topological order of the layers, which is exactly what the search already performs. Doing it during relaxation is the same work in one pass.

What does NOT work is adding whenever dist[u] + 1 <= dist[v], collapsing the two branches into one. That counts the longer routes as well, and on the example would answer 3 rather than 2 as soon as any longer route exists.

## Why breadth-first search makes ways[u] final before it is used

The search processes vertices in order of distance, so when u is taken from the queue every vertex at distance dist[u] - 1 has already been processed and has contributed everything it will ever contribute to ways[u]. Nothing at distance dist[u] or beyond can contribute, because a shortest route into u arrives from one layer closer. So ways[u] is complete at that moment, which is what makes the single pass sound.

## Magnitude, computed rather than assumed

Two residues below 1000000007 add to at most 2000000012, and the limit of a signed 32 bit integer is 2147483647, so the addition fits with about seven per cent to spare. Nothing here multiplies two counts, so no wider type is needed. Take the modulus after every addition rather than at the end, or the running total does leave 32 bits.

## Cost

O(n + m), one search, with O(n) memory for the two arrays.

Constraints - `1 ≤ n ≤ 50000` - `0 ≤ m ≤ 100000` - `1 ≤ u, v ≤ n`