1674. Cheapest Routes That Pass a Checkpoint

An undirected graph has n vertices and m weighted edges, every weight at least 1. One vertex x is a CHECKPOINT. Print how many routes from vertex 1 to vertex n have the smallest possible total weight AND pass through x, reduced modulo 1000000007.

Print 0 when there is no route at all, and also when no cheapest route goes through x.

``` 5 vertices, checkpoint 4 1 - 2 (1) 1 - 3 (1) 2 - 4 (1) 3 - 4 (1) 4 - 5 (1) 1 - 5 (3)

-> 2 ```

Three routes cost 3: 1 - 2 - 4 - 5, 1 - 3 - 4 - 5 and the single edge 1 - 5. Two of them pass through vertex 4. With the checkpoint set to 2 the answer is 1 instead.

## The four things that have to be said

directed? no. Every edge may be walked either way. self-loops? allowed, and never on a cheapest route. parallel edges? allowed, and two copies of the same weight are two routes. unreachable? yes, and the answer is then 0. The checkpoint may also be reachable while lying on no cheapest route, which is also 0. When n is 1 the only possible checkpoint is vertex 1 and the answer is 1.

## What most people try first

Counting the cheapest routes with problem 1672's method and then asking which of them touch x. The count knows nothing about which vertices were used; it is one number per vertex, and the routes it summarises were never built.

The second instinct is to delete every vertex except x and its neighbours, or to force the route through x by splitting the search in two and multiplying the DISTANCES. The distance split is the right idea and the multiplication is in the wrong place: distances add, counts multiply.

## Two searches, then one multiplication

Run the counting Dijkstra of problem 1672 twice:

from vertex 1: ds[v], cs[v] cheapest cost and count of routes 1 -> v from vertex n: dt[v], ct[v] cheapest cost and count of routes v -> n

On an undirected graph the second is just the search from n. Then

if ds[n] is infinite: answer 0 else if ds[x] + dt[x] != ds[n]: answer 0 else: answer (cs[x] * ct[x]) mod 1000000007

## Why the product is right, and why it does not double count

The condition ds[x] + dt[x] == ds[n] is exactly the condition of problem 1670 for x to lie on some cheapest route. When it holds, every cheapest route through x splits uniquely at x into a cheapest route from 1 to x and a cheapest route from x to n: uniquely, because a route visits x exactly once, which positive weights guarantee by making every cheapest route simple.

And every pairing of such halves glues into a cheapest route, by the same argument as in problem 1670: the glued walk costs ds[n] and a minimum-cost walk cannot repeat a vertex, since cutting the repetition out would cost strictly less.

So the cheapest routes through x are in one-to-one correspondence with the PAIRS, and the number of pairs is the product. The uniqueness of the split is what rules out double counting, and it is the step that would fail if a weight could be 0.

## Magnitude, computed rather than assumed

This is the one problem in the group that MULTIPLIES two counts. Each factor is below 1000000007, so the product reaches about 10^18. That is far past the 2147483647 a signed 32 bit integer holds, so the multiplication must be done in 64 bits and reduced immediately. A signed 64 bit integer holds 9223372036854775807, so 10^18 is comfortable there, but only just over nine times so: a product of three such counts would not fit.

The distances need 64 bits as well, for the usual reason: a simple route of 49999 edges at 10^9 reaches 5 * 10^13.

## Cost

Two Dijkstra runs, O(m log n), then constant work. Memory is O(n + m).

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