On Wed, May 11, 2011 at 3:20 PM, Bin Jin <bjin1990@gmail.com> wrote:

Hi, cafe

I'm recently solving some algorithm puzzles from previous Google Code Jam rounds, and today I met some problem I can't solve now.
It's a problem (Round 3 2010, B) that the solution require to find a shortest path in a graph with about 100,000 vertices
and 50 edges from each vertex. Apart from find shortest path, I find that building graph also takes a lot of time.
Yes, I know it's unnecessary to dump the entire graph to the memory, but I want to know if it's possible to build such graph in some reasonable time.

following is a snippet of code building the graph, runs about 15 mins on Core 2 Duo 2.40GHz without any RTS flags

>
> import Data.Array
>
> main = graph `seq` putStrLn "Finished"
>
> n = 100000
> bnds = (0, n-1)
>
> buildGraph bnds edges = accumArray (flip (:)) [] bnds edges
>
> graph = buildGraph bnds edges
>
> edges = [ (i, (y, 1 - x::Int))
>         | i <- range bnds
>         , j <- [2..50]
>         , let (x, y) = if i + j >= n then (1, i + j - n) else (0, i + j)
>         ]
>

Regards,
Bin Jin