Initially I’ve solved the problem using graph Data Structure, and finding the leaf node (or) last neighbour from each node, and given the minimum of all nodes value, but it fails because of Time.

So i have modified to use Matrix and after long time, it reduced to or came similar to All Path Shortest Path. But it gives me less value than actual result. Fails from Test case 4 (also processing Time Out For Testcase 5).

Because one of the tests declares a large amount of edges (~52K) using an adjacency list to represent the graph is much better than the adjacency matrix as you will get an OutOfMemory exception with the matrix.

The algorithm is quite simple, all you need is iteratively playing with leaf edges (or nodes)

Adjacency list also fails for test cases as its taking too much time, and thats why i went for matrix as optimization. I’ve used python, with objects. does that causes overhead in running time?

My solution is in Java and if adjacency lists didn’t work for you in Python then it’s either an issue with your algorithm or in the way how large data sets are handled/accessed in Python.
If I were to store the 52K nodes in an adjacency matrix using one byte for each node then, unless using a sparse matrix structure, I would need ~2.5GB of heap.

Anyway, it was just a recommendation - feel free to use any approach that works for you.

Hi I am using python too, but I am using a dictionary to implement the adjacency list, so if I am given the next edges:
1 2
1 3
2 4
2 6
4 5
I would have the next dictionary:
{1:[2,3], 2:[4,6], 3:[1], 4:[5], 5:[4], 6:[2]}

Update: yes I missed some children in 2 and 4, it is like you wrote:
{1:[2,3], 2:[1,4,6], 3:[1], 4:[2,5], 5:[4], 6:[2]}

is it optimal or there is a better implementation? I having problems to pass the last test.

Because the graph is not oriented there seems to be a bug in your implementation. The list should look like:
{1:[2,3], 2:[1,4,6], 3:[1], 4:[2,5], 5:[4], 6:[2]}

I’ve only managed to get 7/10 and I would really like to get 100% so if you had any advice that would be great! My algorithm requires going through all the values twice and I think that could be what’s slowing me down. Is it possible to reduce this?

Also I’m storing the connections using 2 lists (so list1[x] and list2[x] have a connection). Should I switch to a dictionary? Is that more efficient?

Except for the page formatting which can have issues at times (not always, that’s the trick…), we are not able to reproduce the “company not found” errors.

Could you send a screenshot and scenario at coders@codigname.com? (Browser?, are you logged-in when submitting?, when does the error occur?).