Efficient Data Structure for holding a graph

Question

Problem Link - http://opc.iarcs.org.in/index.php/problems/NUMTRIPLE

In my opinion, the problem can be solved by a data structure, that shows how each number is connected to another, and via recursion find the smallest possible value. But my question is, what data structure (most efficient) can hold/represent such data? Also, is there a better (faster) way of solving this problem.

Thanks

• DeveloperDon: Thank you for your first post to Stack Exchange Programmers. Please consider revising your question title to help people know what it is about without drilling down into the comments and the problem link. Given this question seems to be part of a competition, is it ethical to ask for help on this site? Additional guidelines for questions can be found in the FAQ at programmers.stackexchange.com/faq
• 7Aces: The question is pretty specific to the given problem, so it seems like a conundrum to find a better title. It is just a preparation Q and is not part of a competition. Appreciate the concern...
• user40980: Please strive for a better title. "Efficient Data Structure for this particular problem" doesn't tell me anything about what the problem is when reading through question listings or rss feeds.

Answer 1

The problem is equivalent to the shortest-path problem in a graph, where the vertices are given by the first and third number of each of your triples, an edge is given by a triple "connecting" two vertices, and the weight of the edge is given by the second number of each triple. It can be efficiently solved, for example, by Dijkstra's algorithm. The Wikipedia article lists some different heap data structures for graphs which may be appropriate for this algorithm as long as the graph is "sparse".

Answer 2

multidimetional array, we can also call it matrix.

create nxn dimentional array (lets say A) - where n is number of node in graph. when node i and j is connected set A[i][j] to 1 else set to 0.