# Given complete graph, find optimal path with two costs on each edge

We are given complete graph, such that each edge has two costs $$a \text{ and } b$$. We should find path that passes through each node once and has minimum total cost. Cost of a path is the maximum of both of the sums $$a$$ and $$b$$ of the edges laying on the edges crossed on the path.

One person told me that this is easily solvable by taking the maximum of $$a \text { and } b$$ for each edge and then using the dynamic programming technique storing the final index and the bitmask of visited nodes. I couldn't find a counter test case, however I'm not sure if this is correct approach.

• Can you add a reference to the original problem? – Apass.Jack Jun 14 at 22:33
• I don't have reference this time, since this was a problem I saw at one programming camp, however there wasn't any resource mentioned and the problems are not being published online. – someone12321 Jun 15 at 11:10
• What is "the maximum of both of the sums 𝑎 and 𝑏 of the edges laying on the edges crossed on the path"? Can you add a simple non-trivial example in the question?? – Apass.Jack Jun 16 at 8:04
• Say you choose one path (that goes through each node once) of the complete graph. On this path keep two variables, one is the sum of all a values on this path, and the other one is the sum of all b variables on this path. Then the cost of this path is the maximum of those two sums. – someone12321 Jun 16 at 8:12