Answers to: HISPDNET algorithmhttps://inoi15.discuss.codechef.com/questions/61499/hispdnet-algorithm<p>Problem statement: <a> </a><a href="http://opc.iarcs.org.in/index.php/problems/HISPDNET">http://opc.iarcs.org.in/index.php/problems/HISPDNET</a> </p>
<p>I can only think of the following:</p>
<p>1) Brute force: Consider all permutations of 2,3,4,...,N and find which among these gives the minimum cost (where the 1st city of the permutation is connected only to 2nd element, 2nd element to 3rd element and so on). But it is too time consuming and wouldn't give the answer even in a billion years.</p>
<p>2) Use some shortest path algorithm. (As of now, I am only familiar with Dijkstra's and Floyd Warshall). But there is a big restriction, I need to find shortest paths between all pairs of sources and destinations and where the number of intermediate edges is strictly N-2 (excluding source and destination), nothing more or nothing less.</p>
<p>I am really confused as to how to approach the problem with an elegant time efficient algorithm. It would be great if someone could give me a hint.</p>enThu, 21 Feb 2019 07:09:12 -0000