Problem description here.
Problem summary
You have to add exactly K (≥1) vertical edges (with cost 0) among the two rows of nodes such that total diameter of the connected graph is minimum. The number of vertices in top and bottom row is equal and at most 12. So total vertices can be 24. Adjacent edge costs of top and bottom row are also given.
Solution
The brute force idea is to iterate through every possible subsets of vertical edges and choose such subsets that have K vertical edges. Then run Floyd-warshall algorithm in the original graph with K additional vertical edges (cost 0). To iterate through the subsets, bit mask or backtracking can be used. Running time: O( (212)*24*24*24 )
Practice code is given below:
Discussion Forum 