sorry, it's 15 seconds. It's a typo<br><br><div class="gmail_quote">On Wed, May 11, 2011 at 3:20 PM, Bin Jin <span dir="ltr"><<a href="mailto:bjin1990@gmail.com">bjin1990@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Hi, cafe<br><br>I'm recently solving some algorithm puzzles from previous Google Code Jam rounds, and today I met some problem I can't solve now.<br>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 <br>
and 50 edges from each vertex. Apart from find shortest path, I find that building graph also takes a lot of time.<br>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.<br>
<br>following is a snippet of code building the graph, runs about 15 mins on Core 2 Duo 2.40GHz without any RTS flags<br><br><blockquote style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204, 204, 204);padding-left:1ex" class="gmail_quote">
> <br>> import Data.Array<br>> <br>> main = graph `seq` putStrLn "Finished"<br>> <br>> n = 100000<br>> bnds = (0, n-1)<br>> <br>> buildGraph bnds edges = accumArray (flip (:)) [] bnds edges<br>
> <br>> graph = buildGraph bnds edges<br>> <br>> edges = [ (i, (y, 1 - x::Int))<br>> | i <- range bnds<br>> , j <- [2..50]<br>> , let (x, y) = if i + j >= n then (1, i + j - n) else (0, i + j)<br>
> ]<br>><br></blockquote><br>Regards,<br><font color="#888888">Bin Jin<br>
</font></blockquote></div><br>