1677. The Cheapest Cost and How Many Achieve It
An undirected graph has n vertices and m weighted edges, every weight at
least 1. Print TWO numbers on one line: the smallest total weight of a route
from vertex 1 to vertex n, and how many routes achieve it, reduced modulo
1000000007.
If there is no route, print -1 0.
``` 4 vertices 1 - 2 (1) 2 - 4 (1) 1 - 3 (1) 3 - 4 (1) -> 2 2
4 vertices 1 - 2 (10) 2 - 4 (10) 1 - 3 (1) 3 - 4 (1) -> 2 1 ```
The two graphs have the same cheapest cost and different numbers of routes achieving it, which is why the pair is more informative than either number alone.
## 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 then BOTH values are printed: -1 for the cost and 0
for the count. When n is 1 the answer is "0 1": a route of no
edges, costing nothing, and there is one of it.
## Why the two numbers have different sentinels
This is the detail worth getting right, and it is a formatting decision with a
reason behind it. The COST uses -1 because no real cost can be negative here,
weights being at least 1, so -1 is unambiguous. The COUNT uses 0 because the
true number of routes genuinely is zero; a count is a number and there is no
need for a sentinel at all.
Printing -1 -1 or -1 alone would both be defensible, and neither is what is
asked, which is exactly why the output contract is stated apart from the story.
## What most people try first
Two separate searches, one for the cost and one for the count. They are the same search: the count is carried beside the distance and updated in the same relaxation, so running twice does twice the work for nothing.
The second instinct is to compute the cost first and then count the routes by walking the tight edges in a second pass. That is correct and also unnecessary: the walk visits the tight edges in order of distance, which is the order the first search already produced.
## One search carrying two things
dist[1] = 0, ways[1] = 1, everything else infinite with ways 0
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 1000000007
print -1 0 if dist[n] is infinite, else dist[n] and ways[n]
A strict improvement RESETS the count, because the routes counted so far are no
longer cheapest. A tie ADDS. Weights of at least 1 make ways[u] final when
u is settled, since a cheapest route into u arrives from a strictly nearer
vertex that was settled earlier.
## Magnitude, and the two quantities needing different widths
The COST is the one to watch. A cheapest route is simple, so it uses at most
n - 1 = 49999 edges of up to 10^9, reaching about 5 * 10^13. The limit of
a signed 32 bit integer is 2147483647, so the cost needs 64 bits. One weight of
10^9 fits in 32 bits, and so would 2 * 10^9; it is the accumulation that
does not.
The COUNT does not need 64 bits: two residues below 1000000007 add to at most
2000000012, inside 2147483647, and nothing multiplies two counts. Printing them
side by side makes it tempting to give them the same type, which is harmless but
worth knowing is not required.
## Cost
O(m log n) for the one search and O(n) extra memory.
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 two integers on one line separated by a single space: the smallest total weight of a route from vertex 1 to vertex n, then the number of routes achieving it reduced modulo 1000000007. Print -1 0 if no route exists.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.