We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

As noted by others, solving this problem in a manner that does not result in a TLE is tricky. A simple solution of computing the cost counts using DFS/BFS over all of the nodes works only for the simple example case and will time out for all other tests. Nor will Floyd Warshall work here since it provides the only shortest distance between nodes.

One approach that does work within the TLE is to do a DFS/BFS against an arbitrary starting node and in addition capturing the cost difference between it and the other nodes. The difference data can then be used to adjust the data obtained from the DFS/BFS of the reference node to the other nodes. Getting this to work requires a good understanding of graph theory as will as the nuances of the problem statement.

## Toll Cost Digits

You are viewing a single comment's thread. Return to all comments →

As noted by others, solving this problem in a manner that does not result in a TLE is tricky. A simple solution of computing the cost counts using DFS/BFS over all of the nodes works only for the simple example case and will time out for all other tests. Nor will Floyd Warshall work here since it provides the only shortest distance between nodes.

One approach that does work within the TLE is to do a DFS/BFS against an arbitrary starting node and in addition capturing the cost difference between it and the other nodes. The difference data can then be used to adjust the data obtained from the DFS/BFS of the reference node to the other nodes. Getting this to work requires a good understanding of graph theory as will as the nuances of the problem statement.