Let's first decipher the text of the problem to help us figure out which set of conditions the solution needs to satisfy.

We'll notice that the maximum direct distance between any two cities is ~9~, and the speed decrease from each step to the next is ~10 \times~. This gives us an important piece of insight:

If we have two paths, neither of which ends with a ~0~-length edge, the shorter path will always be faster than a longer path – if the longer path has ~k~ steps and the shorter one has ~l~, its last step will take at least ~10^k~ time, while the entire shorter path cannot take more than ~10^{l+1}-1 \le 10^k-1~ time.

From this follows a slightly more general statement:

If we have two paths, the one which is shorter after we trim all trailing zeros from both will be faster. Furthermore, if two paths have the same length after trimming trailing zeros, the one with the smaller distance between the last two cities will be faster than the other. If the two last distances are the same, the one with the shorter second-to-last edge will be faster, etc.

It turns out that there is only one case in which we care about trailing zeros: the problem statement says that from two paths with equal time the preferred one should be the one visiting less cities – the one that has a smaller number of zeros at the end. This gives us a way to simplify the problem: we will start from city ~n-1~ (Beerburg) and calculate which other cities can reach it in ~0~ time and with how many steps. This can be done using a breadth-first search that starts from Beerburg and ignores all non-zero length paths. Let's call this set of vertices ~Z~.

After this, we can run another breadth-first search, this time starting from Beergrade, and find the shortest path to a city belonging to ~Z~. Having in mind our conclusions above, if there is exactly one such path we can be certain that's the answer to the problem. Unfortunately, life is not so simple and there's no guarantee that there will be just one shortest path. So what do we do now?

First, we can assign to each vertex its shortest distance (in terms of the number of edges) from Beergrade – this is easy to do within the breadth-first search algorithm. Let's denote with ~k~ the least number of steps required to reach a vertex in ~Z~ when starting from Beergrade. Then we can apply the following reasoning:

Consider all edges connecting a vertex in ~Z~ to an edge in the set of vertices ~V_{k-1}~ that are exactly ~k-1~ steps away from Beergrade, and then out of them consider the ones that have minimal length. We'll call the set of cities that are connected to ~Z~ through one of these edges ~S_{k-1}~, and for each city ~v \in S_{k-1}~ we'll save two pieces of information:

• ~u_v~ – the vertex in ~Z~ they are connected to through a minimal-length edge.
• ~t_v~ – the minimal number of trailing zeros after they've reached a vertex in ~Z~.

What is so special about the set ~S_{k-1}~? Well, it turns out that the optimal solution has to pass through some vertex ~v~ in ~S_{k-1}~ and then follow its edge ~u_v~ to a vertex that's ~0~ time away from the goal. This is simple to prove: let's assume the opposite is true. Then we'd have to be able to find a path from Beergrade to ~Z~ with less than ~k~ steps, or a path with exactly ~k~ steps that has a shorter last step than all edges connecting ~S_{k-1}~ to ~Z~, or a path with the same number of steps, the same final step and a smaller number of trailing zeros. However, we've constructed the set ~S_{k-1}~ precisely in a way such that none of these conditions can be satisfied.

We can now construct sets ~S_{k-2}, S_{k-3}, \dots, S_0~ in a similar manner:

• Let ~V_i~ be the set of vertices that are exactly ~i~ steps away from Beergrade.
• Take all edges connecting the set ~S_{i+1}~ to ~V_i~. Among those edges, take the ones with minimal length.
• The set ~S_i~ is the set of vertices in ~V_i~ on the end of edges in the previous step.
• For each vertex ~v~ in ~S_i~, we save the city ~u_v~ from ~S_{i+1}~ they are connected to through a minimal-length edge, and ~z_u = z_v~, the number of trailing zeros at the end of its path (if there are multiple candidates for ~u~, break ties in favour of the one with the smallest ~z_u~).

A simple inductive proof similar to the one we've made for the set ~S_{k-1}~ will convince us that the optimal solution has to pass through a city in each ~S_i~. Finally, the set ~S_0~ contains just one city: Beergrade. This gives us the solution, and we just have to iterate through the trail of cities ~u~ to reconstruct it.

Let's calculate the complexity of this solution. Its first two steps are simple breadth-first searches, with complexity ~\mathcal O(m+n)~. How complex is the process of constructing the sets ~S_i~? We can do it by performing a constant number of operations on each city in ~S_{i+1}~ and each edge that has one end in ~S_{i+1}~ – we check whether its other end has distance ~i~ from Beergrade, we find the minimum length in the set of edges satisfying the previous condition, and we compare each edge to the minimum. So the complexity of constructing ~S_i~ is ~\mathcal O(|S_{i+1}|) + \mathcal O(\sum_{v \in S_{i+1}} \deg(v))~. Since no vertex can belong to more than one set ~Z_i~, the total complexity is:

$$\displaystyle \begin{align*} &\mathrel{\phantom=} \mathcal O\left(\sum_i |S_i|\right) + \mathcal O\left(\sum_{v \in S_{i+1}, i \in 0 \dots k} \deg(v)\right) \\ &\le \mathcal O(n) + \mathcal O\left(\sum \deg v\right) \\ &= \mathcal O(n) + \mathcal O(2m) \\ &= \mathcal O(n+m) \end{align*}$$

Reconstructing the path can then take up to ~\mathcal O(n)~ time, and the final complexity is ~\mathcal O(m+n)~.

In terms of memory complexity, we only need a constant additional amount of memory per node, so the memory needed to hold the graph in memory dominates – this is also ~\mathcal O(m+n)~.