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>enFri, 23 Jan 2015 16:15:29 +0530Comment by arpanb8 on sandy999's questionhttps://inoi15.discuss.codechef.com/questions/61499/hispdnet-algorithm#62511<p>Please find the Errors in my code to Compute all the ARTICULATION POINTS in an undirected graph...<a href="http://cpp.sh/5qus">http://cpp.sh/5qus</a></p>arpanb8Fri, 23 Jan 2015 16:15:29 +0530https://inoi15.discuss.codechef.com/questions/61499/hispdnet-algorithm#62511Comment by sandy999 on sandy999's questionhttps://inoi15.discuss.codechef.com/questions/61499/hispdnet-algorithm#61653<p><a href="/users/83893/idraumr">@idraumr</a> <a href="/users/66051/superty">@superty</a> Thanks again! I clicked on your solution link, but ended up blinking at the sight of 'minimum spanning tree.' That's something new. I'll understand how it works and then solve this problem :)</p>sandy999Wed, 14 Jan 2015 17:26:04 +0530https://inoi15.discuss.codechef.com/questions/61499/hispdnet-algorithm#61653Comment by superty on sandy999's questionhttps://inoi15.discuss.codechef.com/questions/61499/hispdnet-algorithm#61521<p>It's a direct application of a certain graph algorithm. I don't think you can do spoiler text here so click here for solution: <a href="http://paste.ubuntu.com/9729050/">http://paste.ubuntu.com/9729050/</a></p>supertyTue, 13 Jan 2015 18:15:21 +0530https://inoi15.discuss.codechef.com/questions/61499/hispdnet-algorithm#61521Comment by idraumr on sandy999's questionhttps://inoi15.discuss.codechef.com/questions/61499/hispdnet-algorithm#61517<p>The actual solution doesn't depend on the algorithm to find articulation points, but you (at least I did) seriously get a lot of intuition to solve this problem efficiently.</p>idraumrTue, 13 Jan 2015 18:03:44 +0530https://inoi15.discuss.codechef.com/questions/61499/hispdnet-algorithm#61517Comment by sandy999 on sandy999's questionhttps://inoi15.discuss.codechef.com/questions/61499/hispdnet-algorithm#61513<p>Oh no! I have no idea about articulation points! I guess I should get familiar with that first before proceeding further. Thanks a lot! :)</p>sandy999Tue, 13 Jan 2015 17:43:56 +0530https://inoi15.discuss.codechef.com/questions/61499/hispdnet-algorithm#61513Comment by idraumr on sandy999's questionhttps://inoi15.discuss.codechef.com/questions/61499/hispdnet-algorithm#61503<p>I'll give you a hint. Do you know how to efficiently find the articulation points in a tree? What's the articulation point in the Government's tree? How do you fix that with the lowest cost?</p>idraumrTue, 13 Jan 2015 16:54:33 +0530https://inoi15.discuss.codechef.com/questions/61499/hispdnet-algorithm#61503