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 :slight_smile:

1 Like