Problem Link - http://opc.iarcs.org.in/index.php/problems/NUMTRIPLEIn 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
Efficient Data Structure for holding a graph
c++;algorithms;data structures
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.