Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question
1  
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 –  DeveloperDon Oct 5 '12 at 0:36
    
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... –  7Aces Oct 5 '12 at 10:10
2  
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. –  MichaelT Nov 6 '12 at 21:19

2 Answers 2

up vote 2 down vote accepted

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".

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.