Submission #3792370

---

Source Code Expand

import Data.List
import Data.Array
import qualified Data.Array.Unboxed as UA
import Control.Monad
import Control.Monad.ST
import qualified Data.Set as S
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as MV

main=interact$show.f.map read.words

f (h:w:r)=sum $ map (\n-> xs V.! n) ar
    where
    (cs,as) = splitAt 100 r
    ca = UA.listArray ((0,0),(9,9)) cs
    ar = filter (\a->a/=1&&a/=(-1)) as
    ds = map (dks ca) (0:[2..9])
    xs = dks ca 1

dks ca 1=runST $ do
    dv <- MV.replicate 10 maxBound :: ST s (MV.STVector s Int)
    MV.unsafeWrite dv 1 0
    let q=S.singleton (0,1)
    dksl ca dv q
    V.unsafeFreeze dv

dksl::UA.Array (Int,Int) Int -> MV.STVector s Int -> S.Set (Int,Int) -> ST s ()
dksl ca dv q
    | S.null q = return ()
    | otherwise = do
        let ((d,u),q') = S.deleteFindMin q
        q'' <- f dv d u q' [0..9]
        dksl ca dv q''
    where
        f _ _ _ q [] = return q
        f dv d u q (v:r) = do
            let a = d + ca ! (v,u)
            lv <- MV.unsafeRead dv v
            if lv > a then do
                MV.unsafeWrite dv v a
                f dv d u (S.insert (a, v) q) r
            else
                f dv d u q r

Submission Info

Judge Result