Hello everyone I need help solving this problem LA 6652 Game Of Thrones The problem comes originally from ACM Regional contest (Dhaka 2013), however in the contest problem set the constraints were smaller (K≤21) which makes the problem easier, however in the version on LA K≤50.

Anyway here are my findings so far

WARNING SPOILER BELOW!

• No cycle exists in the solution, if there were any we can safely remove and obtain a solution of smaller value.
• The solution can be represented as a set of paths, where each path starts and ends at two different nodes from A, if we choose those paths optimally those paths will not overlap on an edge(s) otherwise we can safely remove this edge(s) and obtain a solution of smaller value.

Now the problem becomes minimum cost perfect matching in a complete graph where the graph is formed by the nodes from A, and the edge cost between two nodes is the length of the shortest path between them in the original graph.

I know that this problem can be solved in polynomial time however the algorithm is tedious to implement and hard to understand, so I was wondering if there's another solution which maybe makes use of the properties of the new graph.

Thanks in advance