sorry, it's 15 seconds. It's a typo
On Wed, May 11, 2011 at 3:20 PM, Bin Jin
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