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

×

# Hackerrank Question

 0 Please let me know what is wrong in this code. asked 05 Jul '18, 14:34 1★kjs1124 46●3 accept rate: 12%

One Answer:
 3 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 ! answered 05 Jul '18, 16:46 104●4 accept rate: 20% I got it thnx (06 Jul '18, 09:47) kjs11241★
 toggle preview community wiki:
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