1675. Counting Cheapest Routes Between Every Pair
A DIRECTED graph has n vertices and m arrows, every weight at least 1.
Print an n by n grid where the entry in row i, column j is the number of
routes from i to j of the smallest possible total weight, reduced modulo
1000000007. Print 0 where no route exists, and 1 on the diagonal.
``` 3 vertices, 1 -> 2 (4), 2 -> 3 (1), 1 -> 3 (10)
1 1 1 0 1 1 0 0 1 ```
The entry for 1, 3 is 1: the route 1 -> 2 -> 3 costs 5 and the direct arrow
costs 10, so only one route is cheapest. Problem 1642 prints the DISTANCES for
every pair; this prints how many routes achieve them.
## The four things that have to be said
directed? yes, so the grid is not symmetric and row i column j differs
from row j column i.
self-loops? allowed, and never on a cheapest route, since weights are at
least 1.
parallel arrows? allowed, and two copies of the same weight are two routes.
unreachable? yes, per pair, and that entry is 0. The diagonal is always 1,
the route of no arrows. When n is 1 the whole grid is the
single entry 1.
## What most people try first
Floyd-Warshall with a count matrix alongside the distance matrix, updated in the
same triple loop. That can be made to work and it is delicate, because the
update has to distinguish a strict improvement from a tie in the same place
where the distances are being rewritten, and because the order of the k loop
decides which routes have been accounted for.
There is a simpler correct answer here, and the constraints are chosen to allow
it: n is only 100, so run problem 1672's counting search n times, once from
each vertex, and print the rows as they come out. That is n searches of
O(m log n), about 100 * 2000 * 7 = 1.4 * 10^6 operations, against
O(n^3) = 10^6 for the triple loop. Neither is the bottleneck, and one of them
is much harder to get right.
## The count carried beside the distance
For each source s:
dist[s] = 0, ways[s] = 1, everything else infinite with ways 0
Dijkstra; when u is settled, for each arrow (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
row s is ways[1..n], with 0 wherever dist is infinite
A strict improvement RESETS the count and a tie ADDS, and both happen during
relaxation. Weights of at least 1 make ways[u] final when u is settled,
because a cheapest route into u arrives from a strictly nearer vertex.
## Why the diagonal is 1 and not 0
The route of no arrows from i to i costs 0 and is a route, so there is
exactly one cheapest route and the entry is 1. Setting ways[s] = 1 at the
start is what encodes that, and it is also what makes the whole count work:
every other entry is built from it.
A vertex with a self-loop still has 1 on its diagonal, since going round the loop costs at least 1 and so is not cheapest.
## Magnitude, computed rather than assumed
Two residues below 1000000007 add to at most 2000000012, inside the
2147483647 a signed 32 bit integer holds, and nothing here multiplies two
counts. A cheapest route is simple, so it uses at most 99 arrows of up to
10^6, and a distance stays under 10^8, also inside 32 bits. This is the one
problem in the group where 64 bit arithmetic is genuinely unnecessary, which is
worth knowing rather than assuming either way.
## Cost
O(n * m log n) time and O(n + m) memory beyond the output, since each row
can be printed as soon as its search finishes and no n by n table has to be
held.
Constraints - `1 ≤ n ≤ 100` - `0 ≤ m ≤ 2000` - `1 ≤ u, v ≤ n` - `1 ≤ w ≤ 1000000`
Input
The first line contains two integers n and m.
Each of the next m lines contains three integers u, v and w: a directed arrow from u to v of weight w.
Output
Print n lines of n integers separated by single spaces. The value in row i, column j is the number of cheapest routes from i to j 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.