spoj.pl/problems/SHPATH/15

I know this problem is not going to be easy to get to pass in Java, but I see 3 others have done it, so I know it's possible. I've written an efficient scanner for the input, so that's not my time crunch. I'm wondering what other optimizations can be made to this problem to get it to pass in time. I'm using Dijkstra's with a priority queue as given by this pseudo-code: topcoder.com/tc?module=Stati ... #dijkstra223.

I'm using an array of adjacency list's to store the graph, each of which holds a pair of integers (the node and the distance). I'm thinking if I can remove the overhead of all the object creation of the pairs I might be better off, but I'm not sure how I can do that for this problem without introducing new overhead with division and mod by using a mapping of to a single integer value. Any and all ideas are welcome. Thanks.

Oh, and as a reference, right now my solution runs in ~12 seconds (as determined from testing on TSHPATH).

Hmm, from what I found looks like, as you say, using Java's PriorityQueue will not cut it here. I kind of expected as much, but as I don't have any heap implementations lying around, I was hoping to avoid it. Thanks for the advice.

For any who may find this in the future and are trying the same thing, I'll give some advice on what I had to do to get this solution to pass in Java:

1) Write your own heap for use in Dijkstra's. Java's priority queue is too slow.
2) Store data in parallel data arrays instead of having a pair object (this applies to both storing the adjacency list and the heap).

These were enough, on top of reading the input more efficiently than standard. I played around until I found out how big I had to make my heap, too. That helped so I didn't waste time growing it when necessary. The only run-time instantiation I ended up needing was to create the adjacency list, but doing this as an array instead of an ArrayList was probably the single biggest time saver of the program.