Submission #1777683

---

Source Code Expand

import Data.List
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 :: [Node] -> Int
getDoneNodeIndex nodes = iter (-1) 0
    where
        iter i n
            | n == length nodes                          = i + 1
            | nodeDone node || nodeCost node < 0         = iter i (n + 1)
            | i == -1 || nodeCost node < nodeCost done   = iter n (n + 1)
            | otherwise                                  = iter i (n + 1)
            where
                node = nodes !! n
                done = nodes !! i

calc :: Nodes -> IO ()
calc nodes = do
    list <- getElems nodes
    let i = getDoneNodeIndex list
    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