 # Approach Confirmation for Problem DoubleWeights SRM 685 Topcoder

Hi guys! I was working with this problem here.. I figured that I should add the weights on corresponding edges and then apply Dijkstra’s algorithm. Will this approach work? How should I prove it’s correctness ? I would love to hear your approaches for this problem…

No, this approach will not work because it will not always give the same result as the original weight metric. Consider a simple counter-example as shown below. The outer values are `weight1` and inner ones are `weight2`.

```      (2)
// \\\\
//   \\\\
8//1   1\\\\8
//       \\\\
(0)       (1)
\\\\       //
4\\\\4   4//4
\\\\   //
\\\\ //
(3)
```

By this approach,

``````cost(0-2-1) = (weight1(0-2)+weight2(0-2)) + (weight1(2-1)+weight2(2-1))
= (8+1) + (8+1) = 18
cost(0-3-1) = (weight1(0-3)+weight2(0-3)) + (weight1(3-1)+weight2(3-1))
= (4+4) + (4+4) = 16
``````

However by the method described in the question,
`cost(0-2-1) = (weight1(0-2)+weight1(2-1)) * (weight2(0-2)+weight2(2-1)) = (8+8) * (1+1) = 32 cost(0-3-1) = (weight1(0-3)+weight1(3-1)) * (weight2(0-3)+weight2(3-1)) = (4+4) * (4+4) = 64`

You can still use Dijkstra’s algorithm using the weight1×weight2 metric, however because n will be between 2 and 20, a simple dfs/bfs is the way to go in my opinion 1 Like