Submission #3044582

---

Source Code Expand

{-# LANGUAGE FlexibleContexts #-}

import Control.Applicative
import Control.Monad
import Control.Monad.ST
import Control.Monad.State
import Data.Array.ST
import Data.List
import Data.Array

type Node = Int
type Cost = Int
type Edge = (Node, Cost)
type Graph = Array Node [Edge]

inf = div maxBound 2 :: Int

warshall_floyd :: Graph -> Array (Node,Node) Cost
warshall_floyd graph = runST $ do
  let (s,e) = bounds graph
  dp <- newArray ((s,s),(e,e)) inf :: ST s (STUArray s (Node,Node) Cost)

  forM_ [s..e] $ \i -> do
    writeArray dp (i,i) 0

  forM_ [s..e] $ \i -> do
    forM_ (graph ! i) $ \(j,c) -> do
      writeArray dp (i,j) c

  forM_ [s..e] $ \k -> do
    forM_ [s..e] $ \i -> do
      forM_ [s..e] $ \j -> do
        a <- readArray dp (i,j)
        b <- readArray dp (i,k)
        c <- readArray dp (k,j)
        writeArray dp (i,j) $ min a (b+c)

  freeze dp

main = do
  (h:w:_) <- map read . words <$> getLine :: IO [Int]
  
  graph <- array (0,9) <$>
           (forM [0..9] $ \i -> do
               edges <- zip [0..9] . map read . words <$> getLine :: IO [(Int,Int)]
               return $ (i, edges)
           )
  
  let cost = warshall_floyd graph

  print =<< (sum . concat . map (map ((\x -> if x == -1 then 0 else cost!(x,1)) . read) . words) . lines <$> getContents) 

Submission Info

Judge Result