1672. How Many Cheapest Routes
An undirected graph has n vertices and m weighted edges, every weight at
least 1. Print how many routes from vertex 1 to vertex n have the smallest
possible total weight, reduced modulo 1000000007. Print 0 if there is no
route.
A route is a sequence of edges, so two edges joining the same pair are two routes.
``` 4 vertices 1 - 2 (1) 2 - 4 (1) 1 - 3 (1) 3 - 4 (1) -> 2
4 vertices 1 - 2 (10) 2 - 4 (10) 1 - 3 (1) 3 - 4 (1) -> 1 ```
The second graph has the same shape and only one cheapest route, which is the point: the count depends on the weights and not on the shape.
## 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, since a weight is at
least 1.
parallel edges? allowed, at different weights. Two copies of the SAME weight
are two routes; a dearer copy is not on any cheapest route.
unreachable? yes, and the answer is then 0. When n is 1 the answer is 1.
## What most people try first
Problem 1671's breadth-first search, with the weights ignored. A queue orders vertices by edge count, so it counts the routes with the fewest EDGES rather than the smallest weight, and on the second example above it answers 2 instead of 1.
The second instinct is to count after the search, by walking the tight edges
dist[u] + w == dist[v]. That is correct, and it needs the tight edges visited
in order of distance, which is the order Dijkstra already produces. Doing it
inside the relaxation is the same work in one pass.
## Carry the count, and reset on a strict improvement
dist[1] = 0, ways[1] = 1, everything else infinite with ways 0
Dijkstra from vertex 1; when u is settled, for each edge (u, v, w):
if dist[u] + w < dist[v]: dist[v] = dist[u] + w; ways[v] = ways[u]
if dist[u] + w == dist[v]: ways[v] = (ways[v] + ways[u]) mod 1000000007
A strict improvement RESETS the count, because every route counted so far was
dearer and none of them is cheapest any more. A tie ADDS, because the routes
through u are new.
## Why ways[u] is final when u is settled
Dijkstra settles vertices in non-decreasing order of distance, and every weight
is at least 1, so any cheapest route into u arrives from a vertex at a
STRICTLY smaller distance, which was therefore settled earlier and has already
contributed. Nothing settled later can contribute to ways[u], so the count is
complete at the moment u is settled.
That argument needs the weights to be strictly positive. Problem 1673 is the version with zero weights allowed, where it fails and the one-pass accumulation has to be replaced.
## Magnitude, computed rather than assumed
Two residues below 1000000007 add to at most 2000000012, which is inside the
2147483647 a signed 32 bit integer holds, so the counting arithmetic needs no
wider type and nothing here multiplies two counts.
The DISTANCES are a different matter. A cheapest route is simple, so it uses at
most n - 1 = 49999 edges of up to 10^9, reaching about 5 * 10^13, which
is far past 2147483647. The distances need 64 bits while the counts do not.
## Cost
O(m log n) for the search and O(n) extra memory for the count array.
Constraints - `1 ≤ n ≤ 50000` - `0 ≤ m ≤ 100000` - `1 ≤ u, v ≤ n` - `1 ≤ w ≤ 1000000000`
Input
The first line contains two integers n and m.
Each of the next m lines contains three integers u, v and w: an undirected edge between u and v of weight w.
Output
Print one integer, the number of routes from vertex 1 to vertex n of the smallest possible total weight, reduced modulo 1000000007, or 0 if no route exists.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.