409444: GYM103561 I Dinner Date

It's Valentine's Day, and Rufus is late to his dinner date! Even worse, he forgot to buy a present for his girlfriend.

There are $$$n$$$ intersections in the city, and $$$m$$$ two-way roads connecting the intersections. Rufus is currently at intersection 1. His dinner date is at intersection $$$n$$$.

Whenever Rufus travels along the $$$i$$$th road (between intersections), he visits a store and buys a present for his date with cost $$$w_i$$$. The total cost of his presents is the product of the cost of the presents he buys. He knows his girlfriend loves the number $$$10^k$$$ and will only accept presents if their total cost is divisible by $$$10^k$$$. If Rufus desires, he can revisit the road and purchase the gift another time.

However, Rufus is also very frugal, so he wants the total cost to be as small as possible. Help him find the lowest total cost of all paths from his location to his dinner date where the cost is divisible by $$$10^k$$$.

Since this number, $$$cost$$$, can be very large, output $$$\log_{10}(cost)$$$. If no path exists that satisfies the constraints, output $$$-1$$$. Your answer will be judged as correct if it is within $$$10^{-6}$$$ of the true answer.

The first line contains $$$n$$$, $$$m$$$, and $$$k$$$ where $$$n$$$ is the number of intersections, $$$m$$$ is the number of roads connecting the intersections, and $$$10^k$$$ is the number Rufus' girlfriend loves. $$$(1 \leq n \leq 10^3, 1 \leq m \leq 10^4, 1 \le k \le 10)$$$

The next $$$m$$$ lines contain 3 values $$$u_i, v_i, $$$ and $$$ w_i$$$ where the intersections $$$u_i$$$ and $$$v_i$$$ are connected by a road, and $$$w_i$$$ is the cost of the present on that road. $$$(1 \le u_i, v_i \le n, 1 \le w_i \le 100)$$$

Output $$$\log_{10} (cost)$$$, where $$$cost$$$ is the lowest total cost of all paths from intersection 1 to intersection $$$n$$$, such that $$$cost$$$ is divisible by $$$10^k$$$. If no such path exists, output $$$-1$$$. Your answer will be judged as correct if it is within $$$10^{-6}$$$ of the true answer.

4 4 1
1 2 1
2 3 2
3 4 3
3 4 5

1.0000000000

4 3 1
1 2 1
2 3 2
3 4 3

-1

In the first test case, Rufus wants to purchase gifts at the first, second, and fourth roads, resulting in a total cost of $$$10$$$, and $$$\log_{10}(10) = 1$$$.

In the second test case, there is no way to get from $$$1$$$ to $$$n$$$ and have a total cost divisible by $$$10$$$.