Submission #1777644

---

Source Code Expand

import Data.List
import Data.IORef
import Data.Array
import Data.Array.IO
import Control.Monad

data Node = Node {
    edgesTO   :: [Int],
    edgesCost :: [Int],
    nodeDone  :: Bool,
    nodeCost  :: Int
    } deriving (Show, Eq)
type FNodes = (Array Int Node)
type Nodes  = (IOArray Int Node)

getDoneNodeIndex :: Nodes -> IO Int
getDoneNodeIndex nodes = do
    doneIndex <- newIORef (-1::Int)
    (a,b) <- getBounds nodes
    forM_ [a..b] $ \i -> do
        n <- readArray nodes i
        x <- readIORef doneIndex
        when (not (nodeDone n) && nodeCost n >= 0) $
            if x < 0
                then writeIORef doneIndex i
                else do
                    d <- readArray nodes x
                    when (nodeCost n < nodeCost d) $ writeIORef doneIndex i
    readIORef doneIndex

calc :: Nodes -> IO ()
calc nodes = do
    i <- getDoneNodeIndex nodes
    when (i >= 0) $ do
        done <- readArray nodes i
        writeArray nodes i (done { nodeDone = True })
        forM_ [0 .. length (edgesTO done) - 1] $ \x -> do
            let to      = edgesTO done !! x
            let cost    = nodeCost done + edgesCost done !! x
            node <- readArray nodes to
            when (nodeCost node < 0 || cost < nodeCost node) $ writeArray nodes to (node { nodeCost = cost } )
        calc nodes


calcCost :: Int -> Nodes -> IO Int
calcCost start nodes = do
    s <- readArray nodes start
    writeArray nodes start (s { nodeCost = 0 })
    calc nodes
    list <- getElems nodes
    return $ nodeCost $ maximumBy (\a b -> compare (nodeCost a) (nodeCost b)) list

setNode :: Int -> Int -> Int -> Nodes -> IO ()
setNode n to cost nodes = do
    n1 <- readArray nodes n
    writeArray nodes n (n1 { edgesTO =  edgesTO n1 ++ [to], edgesCost = edgesCost n1 ++ [cost] })
    n2 <- readArray nodes to
    writeArray nodes to (n2 { edgesTO = edgesTO n2 ++ [n], edgesCost = edgesCost n2 ++ [cost] })
    return ()

main :: IO ()
main = do
    [n,m] <- map read . words <$> getLine :: IO [Int]
    input <- newArray (1,n) (Node [] [] False (-1)) :: IO Nodes
    replicateM_ m $ do
        [a,b,t] <- map read . words <$> getLine
        setNode a b t input
    baseNodes <- freeze input :: IO FNodes

    list <- forM [1..n] $ \i -> do
        nodes <- thaw baseNodes
        calcCost i nodes
    print $ minimum list

Submission Info

Judge Result