Skip to content

Instantly share code, notes, and snippets.

@gorlum0

gorlum0/cf25-c.hs

Forked from u1ik/cf25-c.hs
Created August 12, 2011 19:31
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save gorlum0/1142798 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save gorlum0/1142798 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. gorlum0 renamed this gist Aug 12, 2011. 1 changed file with 0 additions and 0 deletions.
    0 cf25-C.hs → cf25-c.hs
    View file
    File renamed without changes.
  2. gorlum0 renamed this gist Aug 12, 2011. 1 changed file with 0 additions and 0 deletions.
    0 C.hs → cf25-C.hs
    View file
    File renamed without changes.
  3. gorlum0 renamed this gist Aug 12, 2011. 1 changed file with 0 additions and 0 deletions.
    0 cf25-c.hs → C.hs
    View file
    File renamed without changes.
  4. @ulan ulan created this gist Aug 18, 2010.
    42 changes: 42 additions & 0 deletions cf25-c.hs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,42 @@
    {-# LANGUAGE NewQualifiedOperators #-}
    import Prelude
    import qualified Data.ByteString.Char8 as B
    import qualified Data.Vector.Unboxed as U
    import qualified Data.Vector as V
    import Data.List
    import Control.Monad
    import Control.Applicative
    import Data.Maybe(fromJust)


    type Graph = V.Vector (U.Vector Int)

    build :: Int -> [[Int]] -> Graph
    build n adj = V.fromList $ map U.fromList $ adj

    relax :: Int -> Graph -> (Int, Int, Int) -> Graph
    relax n g (u, v, c) = V.imap (\i -> U.imap (min . f i)) g
    where
    au = V.(!) g u
    av = V.(!) g v
    f i j = min (U.(!) au i + c + U.(!) av j) (U.(!) av i + c + U.(!) au j)

    combine :: Int -> (Graph, V.Vector Int) -> (Int, Int, Int) -> (Graph, V.Vector Int)
    combine n (g, r) (u, v, c) = (g', V.cons s r)
    where
    g' = relax n g (u, v, c)
    s = V.sum $ V.map U.sum g'

    solve :: Int -> [[Int]] -> [(Int, Int, Int)] -> [Int]
    solve n adj edges = V.toList $ snd $ V.foldl' (combine n) (build n adj, V.empty) (V.fromList edges)

    ints :: IO [Int]
    ints = map (fst . fromJust . B.readInt) . B.words <$> B.getLine

    main = do
    [n] <- ints
    adj <- replicateM n ints
    [k] <- ints
    edges <- replicateM k $ (\(a:b:c:_) -> (a-1, b-1, c)) <$> ints
    let r = reverse $ solve n adj edges
    putStrLn $ intercalate " " $ map show r