https://zeroplusfour.com/toll-cost-digits-hackerrank-solution/ Here's how I did in all languages Java 8 , C++ , C , Python 3, Python 2.

I have not yet found how to solve this within the time limit, but an interesting aside.

Using DFS/BFS on a random start node, when the path reaches back to the start node, then interesting things happen.

Any loop back to the starting node that ends with

loop with
- even number, will yield all possible even numbers
- odd number (except 5) will yield all possible odd numbers
- 5 will yield 0 and 5
- 0 yields 0

So whenever a path circles back to the START, then you can mark all abovementioned paths as already visited.

Given START to START: [0,4]
# means that START->START can be reached on all even numbers [0,2,4,6,8]

Given START->NODE_A = [3]
# means that NODE_A can be reached from START_NODE with a path that end with [3]

# Because START can reach itself with paths ending with [0,2,4,6,8]
# Means we can reach START->NODE_A with [3] + [0,3,4,6,8] =  [3,5,7,9,11] = [ 3,5,7,9,1]

Another interesting mechanic, is that

- count of `1` paths = count of `9` paths
- count of `2` paths = count of `8` paths
- count of `3` paths = count of `7` paths
- count of `4` paths = count of `6` paths
- count of `5` paths NOT = count of `0` paths

I'm trying this out right now, but i believe that you can calculate only the distances from a single node, then be able to infer the distances between all of the other nodes.

(A,B) = [1]
(A,C) = [2]
then (BC) = (AC)+(BA) = [2] + [9] = [11] = [1]
-------
(A,B) = [1,2]
(A,C) = [3,4]
then (BC) = (AC)+(BA) = [3,4] + [1,2] = [3+1,3+4,4+1,4+2] = [4,7,5,6]
--------
(A,A) = [0,1]
(A,B) = [1,2]
(A,C) = [3,4]
(B,C) = (A,A)+(A,C)+(BA) = [0,1] + [1,2] + [3,4] = [0+1+3, 0+1+4, 0+2+3, 0+2+4, 1+1+3, 1+1+4, 1+2+3, 1+2+4]
= [4,5,5,6,5,6,6,7] = [4,5,6,7]

Answering discussions about looping cases such as 2-3 ; 2-3-1-2-3 ; 2-3-1-2-3-1-2-3 .

A cost is used as ending digit only in Solution. Meaing 1, 11, 101,111,201,991 all are same for costs this problem purpose. So unless looping creates costs ending with new digits, looping does not have impact on cost. Suppose a loop is having cost 100. It's equivalent to having cost 0. It does not matter how many times you loop around, it's not going to change ending digit. A looping between nodes of an Edge will give cost of 1000, which is equivalent to 0. This loop does not impact outcome. If problem was for absolute cost, even looping would have impacted outcome very differently, leading to infinite costs. However, in current problem even infinite looping can result only in 10 types of costs.

All pair of (2,3) have costs ending with digit 1 or digit 6, irrespective of looping.

2-3 = 411

2-3-1-2-3= 1476

2-3-1-2-3-1-2-3= 2541

2-3-1-2-3-1-2-3-1-2-3=3606

2-3-1-2-3-1-2-3-1-2-3-1-2-3=4671

so on...

For a given digit you take a pair (x,y) only once. You can take (x,y) pair for all ten digits if you can show paths-costs ending at all possible digits.

In given example pair 2-3 can be counted only for digit 1 and digit 6. Basically this loop costs 1065, which ends in digit 5. So in each second loops the cost will be 10 making total cost ending at same digit as no-loop iteration. Looping adds only one extra digit, it does not create all random possilities.

Suppose for a given pair of (x,y) a there is a loop cost ends at 1, in that case looping will add one digit each iteration. x,y pair will have costs ending in all 10 digits.

Suppose for a given pair of (x,y) a there is a loop cost ends at 2, in that case looping will add 5 more costs of type.

the vast majority of test cases do not even tolerate DFS, which simply iterate over nodes without doing anything useful yet... I am confused.

Illustrate algorithm: https://shortnewsinfo.com/35zeq6