OJ Board

After observing that I was pushing a node more than once in my queue ring, and that my program was wasting time trying to update neighbor nodes from such repeated nodes, I reduced the execution time and finally got Accepted.

Well, no one replied to this post, but it might be helpful to someone else ...

... Today I found a good idea to implement Dijkstra's algorithm when you know that the edge weights in the graph are in a certain range, say [0,k), using k simple queues. This improves the relaxation step from O(log (n)) to O(1).

However, I am still getting TLE. Here is my new code:

EDIT: code ...

I have been trying to solve problem 3652 (Lazy Jumping Frog) from the Live Archive, but I keep on getting Time Limit Exceeded.

I am using Dijkstra's algorithm to solve it. My code is written in C++, and I'm using the "set" data structure from the STL to get the node with the shortest distance to ...

I had already thought about what you told me Jan, so I removed the last two newline chars and submitted it back, but still got WA. After a while, I decided to remove only the very last newline char and got AC.

I think the judging for this problem must be corrected, since it should give PE as ...

I have written a solution for this problem, and I'm sure the formula I use is correct, yet I keep on getting WA on the new uva judge site.

Here is my code:

Code removed...

Can anyone tell me or provide a hint as to why I keep on getting WA?[/quote]

... for which your problem fails to give out the correct answer:

Input:

3
0,01
0,03
0.03
12
123.12
6.13
9.44
89.08
278.78
223.78
78.45
912.89
554.76
547.57
1781.89
907.07
15
0.01
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03


Correct output:

$0.01
$2407.09
$0.01 ...

... you should read the problem over and over again until you understand it thoroughly. Any attempt to code a solution before understanding the problem is doomed to fail.

This, in fact, may also help you in making your code shorter, or cleaner, or maybe even both.

Good luck!

The correct outputs for the inputs:


3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
3
6.17
5.00
4.03
12
123.12
6.13
9.44
89.08
278.78
223.78
78.45
912.89
554.76
547.57
1781.89
907.07
2
4.99
15.00
1
10.00
15
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.03
5
5000.00
11.11
11 ...

... I have seen several codes which do the same thing to parse the input for this problem. They read the money into a double, multiply it by 100 and then store the result into an integer. I think this may be a source of rounding errors, since I found that in one of my test cases 12.9 got converted ...

... the way you're converting a double into an integer while reading the input. I had a similar problem in my first version coded in C (you're coding in C++, so I'm not sure if the same problem is present). For example, with the input:


3
12.9
12.14
4.32
0


the value of 12.9 I obtained after ...

I've been checking all possible details in my code, but I keep on getting WA on this problem. I would be very thankful if someone could check out my code and make a suggestion... Thanks in advance.


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX ...