You are not logged in. Please login at to post your questions!


Hackerrank Question

Your Implementation of was absolutely correct but the reason for some failing cases was the following block of code:

  node x = nodes[nn.dest].get(i);
  if(dist[nn.dest]+x.dist< dist[x.dest] )
          dist[x.dest] = dist[nn.dest]+x.dist;
              long r = (dist[nn.dest]%k);
              dist[x.dest] += k-r;
          node xx = new node();

You are adding the extra waiting time only after you have considered that the current path is shorter than the path , What I mean to say is that you are not adding the extra waiting time before putting elements in your queue.

Let us consider an example , suppose you reach a node at time t = 4 and the weight of the edge that you will be traversing is just 1 unit. Now suppose that the traffic light is red at t = 4 when you reached the node , but since you do not consider the extra waiting time during the if(dist[nn.dest]+x.dist< dist[x.dest] ) statement , your code fails on some cases

I modified your code , check it. I just did the following modification to your code:

         long tempp = 0;
             long r = (dist[nn.dest]%k);
              tempp += k-r;
           if(dist[nn.dest]+x.dist + tempp < dist[x.dest] )
            dist[x.dest] = dist[nn.dest]+x.dist + tempp;

                node xx = new node();


Since we now consider the extra waiting time in the variable tempp , It passes all the cases where it failed. I hope I was Able to help you , you can check a neat implementation of this question in c++ here. Thank You !


answered 05 Jul '18, 16:46

pieliedie's gravatar image

accept rate: 20%

I got it thnx

(06 Jul '18, 09:47) kjs11241★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 05 Jul '18, 14:34

question was seen: 166 times

last updated: 06 Jul '18, 09:47