I'm getting WA in problem spoj.pl/problems/TRAFFICN/I have used dijkstras two times , kindly provide me test case for which I'm wrong
here is the code
removed
1 4 4 0 1 4 1 2 10 1 3 1 2 4 10 3 4 1
Check documentation on priority_queue.
Its Accepted .. Thank you ... but in 0.86 sec and your solution is taking just 0.27 sec , I was wondering how would you've done . So please tell me your approach so that I can reduce time further .
Thanks
If I would use some special algo, I wouldn't be telling about it
In case of this problem it's just standard optimalisation. Fast input: buffered reading + processing char by char + fast multiplication by 10 using a*10==(a<
a*10 should be faster than (a<reason: in assembly level, a*10 is one instruction (MUL) where (a << 3 ) + (a << 1) is 3, (SHL, SHL, ADD). each of them use single clock pass (according to X86 architecture).
In addition to zukow's post, write a manual heap with standard array, it's small...
Okay ... Thank you Hasan and Zukow for your suggestions , I needed them .
Ok, I never actually checked that I just read this one on the forum and assumed MUL uses more ticks. Either way, it didn't make any difference for runtime on this problem.
Why are we reversing the edges and applying dikjstra’s algo