You are not logged in. Please login at www.codechef.com 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;
          if((dist[nn.dest])/k%2==1){
              long r = (dist[nn.dest]%k);
              dist[x.dest] += k-r;
          }
          node xx = new node();
          xx.dest=x.dest;
          xx.dist=dist[x.dest];
      queue.add(xx);
   }

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;
         if((dist[nn.dest])/k%2==1){
             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();
                xx.dest=x.dest;
                xx.dist=dist[x.dest];
                queue.add(xx);
           }

        }

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 !

link

answered 05 Jul '18, 16:46

pieliedie's gravatar image

5★pieliedie
1044
accept rate: 20%

I got it thnx

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

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×180

question asked: 05 Jul '18, 14:34

question was seen: 166 times

last updated: 06 Jul '18, 09:47