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
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
