You are not logged in. Please login at www.codechef.com to post your questions!

×

HISPDNET algorithm

Problem statement: http://opc.iarcs.org.in/index.php/problems/HISPDNET

I can only think of the following:

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.

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.

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.

asked 13 Jan '15, 16:16

sandy999's gravatar image

3★sandy999
39111537
accept rate: 10%

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?

(13 Jan '15, 16:54) idraumr0★

Oh no! I have no idea about articulation points! I guess I should get familiar with that first before proceeding further. Thanks a lot! :)

(13 Jan '15, 17:43) sandy9993★

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.

(13 Jan '15, 18:03) idraumr0★
1

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: http://paste.ubuntu.com/9729050/

(13 Jan '15, 18:15) superty3★
1

@idraumr @superty 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 :)

(14 Jan '15, 17:26) sandy9993★

Please find the Errors in my code to Compute all the ARTICULATION POINTS in an undirected graph...http://cpp.sh/5qus

(23 Jan '15, 16:15) arpanb83★
showing 5 of 6 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×9

question asked: 13 Jan '15, 16:16

question was seen: 520 times

last updated: 23 Jan '15, 16:15

Related questions