Loading...
Loading...
Loading...
A courier moves between n towns joined by m two-way roads "a b w" with positive cost w. From town 1 to town n, print the lowest total cost and the number of different routes with exactly that cost. Two routes differ if they use a different list of roads. Print the number modulo 1000000007. If town n cannot be reached, print -1.
Example
Input
4 4 1 2 1 1 3 1 2 4 1 3 4 1
Output
2 2
Two routes of cost 2: through town 2 or through town 3.
Try the problem first. Open one hint at a time.
Run Dijkstra and keep ways[v], the number of cheapest routes to v.
On a strictly better distance copy ways[u]; on an equal distance add ways[u]. Take the modulus each time.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor