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
3
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”.
0
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.