Nov 2008
1 / 6
Nov 2008
May 2022
knightry
Nov '08

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).

  • created

    Nov '08

  • last reply

    May '22
  • 5

    replies

  • 1.2k

    views

  • 4

    users

  • 3

    links

MAK_sof
Nov '08

I think there is a much older thread in this forum that explains various approaches for getting AC in this problem. I coded my own heap instead of using any built in data structures (e.g. PriorityQueue in Java). Using a priority_queue or set got me TLE even in C++.

knightry
Nov '08

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.

knightry
Nov '08

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.

11 years later
vin_win
May '20

Passed in 1.07 seconds.

I used Java’s Priority Queue.

I was getting TLE when I used Java’s HashSet (to keep track of visited nodes) and Java’s HashMap (to store graph)

Only when I removed the HashSet ( because I realized djikstra can be done without it) and used array of ArrayList (to represent graph) did I get an AC.

So overall,
Fast IO + Java’s Priority Queue + array of ArrayList = AC

I got this idea thanks to Long Tran :

2 years later
paz
May '22

At first I have tried Java’s priority queue, and incorrectly assumed that the graph is dense - results were TLE. Then I implemented dedicated priority queue with decrease-key operation and got AC (pretty slow however: 1.48). For storing graph I was using arrays.