1676. Counting Routes Modulo Whatever You Are Given
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
total weight, reduced modulo p, where p is GIVEN IN THE INPUT. Print 0 if
there is no route.
p need not be prime, and it may be 1, in which case every answer is 0.
``` 4 vertices, p = 1000000007 1 - 2 (1) 2 - 4 (1) 1 - 3 (1) 3 - 4 (1) -> 2
the same graph with p = 2 -> 0 ```
## 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. When n is 1 the answer is
1 mod p, which is 0 when p is 1 and 1 otherwise.
## What most people try first
Problem 1672's method with 1000000007 swapped for p. That is very nearly
right, and the two details it gets wrong are the whole lesson.
The first is the initial count. ways[1] must be 1 mod p, not 1. With p = 1
every residue is 0, and writing a bare 1 there makes the answer 1 when it should
be 0.
The second is more serious and more interesting: a modular count cannot be used for anything except printing.
## Why a count modulo p tells you nothing about whether routes exist
0 is the answer both when there are no cheapest routes and when the number of
them happens to be a multiple of p. The graph above with p = 2 has two
cheapest routes and prints 0.
So reachability must be decided by the DISTANCE, never by the count. A method
that prints the count and relies on it being non-zero to mean "a route exists"
is wrong for every composite p and for every prime smaller than the true
count.
## Why nothing here may be divided
A tempting shortcut for counting is to compute a total and divide out a repeated
factor. Division modulo p needs the divisor to be invertible, which needs it
to be coprime to p, and p here is arbitrary. With p = 4 the value 2 has no
inverse at all, so no amount of care rescues the idea.
That is why the accumulation has to be purely ADDITIVE: reset the count on a strict improvement, add on a tie, and never form a quantity you later have to undo.
dist[1] = 0, ways[1] = 1 mod p
Dijkstra; 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 p
print 0 if dist[n] is infinite, else ways[n]
## Magnitude, computed rather than assumed
Two residues below p add to at most 2p - 2, which at p = 10^9 is
1999999998. The limit of a signed 32 bit integer is 2147483647, so even the
largest allowed modulus leaves the addition inside 32 bits, with about seven per
cent to spare. Nothing here multiplies two counts, so no wider type is needed
for them.
The DISTANCES do need 64 bits: a cheapest route is simple, so at most
n - 1 = 49999 edges of up to 10^9 reach about 5 * 10^13.
## Cost
O(m log n) and O(n) extra memory, exactly as in problem 1672. Making the
modulus a variable costs nothing at run time; it costs the two correctness
details above.
Constraints - `1 ≤ n ≤ 50000` - `0 ≤ m ≤ 100000` - `1 ≤ p ≤ 1000000000` - `1 ≤ u, v ≤ n` - `1 ≤ w ≤ 1000000000`
Input
The first line contains three integers n, m and p.
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 smallest-total-weight routes from vertex 1 to vertex n reduced modulo p, or 0 if no route exists. Note that 0 does not by itself mean there is no route.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.