title: Shortest Distance from Leaf to Root of a Directed tree
body: <p>Here is a very interesting problem which I have encountered: there is a directed tree in which the weight of each node changes with time and I have to find the distance from the root to some node.</p>
  
  <p><strong>Problem Statement:</strong></p>
  
  <ul>
  <li>There’s a long queue in front of a ticket counter. Here are the queue
  considerations.</li>
  <li>There can be max 2 incoming queues merging at a junction point</li>
  <li>There can be only one outgoing queue from any junction point</li>
  <li>There can be multiple junction points &amp; the queues move
  uni-directionally</li>
  <li>There will be only one final ticket counter point to which all the
  queues lead</li>
  <li>There are multiple entry points for the fans to reach the
  counter</li>
  <li>I need to design a system that can suggest to the fans the
  “Optimal Path” and its “Expected Time" to reach the counter</li>
  </ul>
  
  <p>The expected time to reach the counter from a queue depends on the number of people in that queue plus the number of people in the other queues.</p>
  
  <ul>
  <li>Time taken to cross the ticket counter and receive the ticket is 1
  time unit</li>
  <li>Assume that there is a policeman standing at each junction point
  whose job is to open the junction gate to send people from the
  in-queue(s) to the out-queue . If there are multiple in-queues for a
  junction, the policeman will send fans from each queue one by one
  alternatively</li>
  </ul>
  
  <p>For example, if there are 2 in-queues containing 3 fans each, the leading person from queue1 will be sent in first, followed by the leading person from queue2, followed by next person from queue1 and so on. It’s an alternate pick between the incoming queues.</p>
  
  <p><a href="https://www.hackerearth.com/walmartlabs-java-developer-hiring-challenge/algorithm/ticket-counter-8/description/" rel="nofollow noreferrer">Full Problem Statement</a></p>
  
  <p>For a Given Input</p>
  
  <ul>
  <li>The first line contains the number of junctions</li>
  <li>The second line contains the number of queues</li>
  <li>The next 'e' lines contain three values: the start junction, the end
  junction and the number of people on this queue. (This is also the maximum number of people that can stand in this queue.)</li>
  </ul>
  
  <p>Calculate the <strong>minimum time</strong> for a person to reach the ticket counter who is just about to enter any queue. Also, output the <strong>path</strong> that he should take to reach the counter in minimum time in the worst case (at each junction point, the policeman starts choosing people from the in-queue other than the one we are calculating the minimum time for).</p>
  
  <p><strong>How can one solve this type of time-varying problem?</strong></p>
  
  <p>For Example:</p>
  
  <pre><code>7
  6
  1 5 9
  2 5 5 
  3 6 1
  4 6 3 
  5 7 7 
  6 7 4
  </code></pre>
  
  <p>Graph Looks Like This: 
  <a href="https://i.stack.imgur.com/FAldW.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/FAldW.jpg" alt="enter image description here"></a></p>
  
  <h2>Ticket counter point: 7</h2>
  
  <h2>Entry points: 1, 2, 3, 4</h2>
  
  <ul>
  <li>Time required for a person who is just entering the queue from entry
  point 3: 1 person from queue(3,6) + 2 people from queue(4,6) + 4
  people from queue(6,7) + 7 people from queue(5,7) + 1 person from
  queue(1,5) will go before this person. <br><br></li>
  </ul>
  
  <h2>Optimal time = 15</h2>
  
  <h2>Path is 3 -> 6 -> 7</h2>