OJ Board

I still wonder how people get this calculated in under 0.002s..

What worked for me was to first cache pairs (c, d) for every x: 1..20'000'000 such that
x = 2^a * 5^b * r;
c = a - b; // easily calculated
d = r % 10;

Then considering:
if x -> (c, d) then lastnonzerodigit(x) = { d, if c = 0 | 5, if ...

Gradient descent with centroid as a starting point works well too.
Is there a geometrical solution though?

A simpler example where single Floyd-Warshall is too greedy: it discards shorter path over city 3 because it's expensive to party there, even though a more expensive city (5) is inevitably encountered later.

5 5 1
10 10 20 10 30
1 2 2
1 3 1
2 4 2
3 4 1
4 5 5
1 5

I'm guessing running the ...