1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

using System;

namespace Hef.TopCoder.Srm144.Div2
{
  public class PowerOutage
  {
    public int estimateTimeOut(int[] fromJunction, int[] toJunction, int[] ductLength)
    {
      // we will have to enter and exit every junction...
      int totalLength = 0;
      foreach (int dl in ductLength)
      {
        totalLength += dl * 2;
      }

      // ...except for the ones on the path that is farthest from the entrance
      totalLength -= calcMaxDepth(0, fromJunction, toJunction, ductLength);

      return totalLength;
    }

    int calcMaxDepth(int id, int[] fromJunction, int[] toJunction, int[] ductLength)
    {
      int maxDepth = 0;

      for (int i = 0; i < fromJunction.Length; i += 1)
      {
        if (fromJunction[i] == id)
        {
          maxDepth = Math.Max(maxDepth, ductLength[i] + calcMaxDepth(toJunction[i], fromJunction, toJunction, ductLength));
        }
      }

      return maxDepth;
    }
  }
}