Submission #1777304


Source Code Expand

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

data Node = Nil | 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


getCost :: Int -> Nodes -> IO Int
getCost start nodes = do
    s <- readArray nodes start
    writeArray nodes start (s { nodeCost = 0 })
    calc nodes
    maxCost <- newIORef (-1::Int)
    (a,b) <- getBounds nodes
    forM_ [a..b] $ \i -> do
        n <- readArray nodes i
        m <- readIORef maxCost
        when (nodeCost n > m) $ writeIORef maxCost (nodeCost n)
    readIORef maxCost

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

    minCost <- newIORef (maxBound :: Int)
    forM_ [1..n] $ \i -> do
        nodes <- thaw baseNodes
        nc <- getCost i nodes
        mc <- readIORef minCost
        when (nc < mc) $ writeIORef minCost nc

    print =<< readIORef minCost

Submission Info

Submission Time
Task D - バスと避けられない運命
User atctk
Language Haskell (GHC 7.10.3)
Score 0
Code Size 2657 Byte
Status TLE
Exec Time 5258 ms
Memory 35196 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 35
TLE × 4
Set Name Test Cases
All sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt
Case Name Status Exec Time Memory
sample_01.txt AC 2 ms 508 KB
sample_02.txt AC 2 ms 508 KB
sample_03.txt AC 2 ms 508 KB
test_01.txt AC 2 ms 508 KB
test_02.txt AC 305 ms 1148 KB
test_03.txt TLE 5258 ms 35196 KB
test_04.txt AC 228 ms 2428 KB
test_05.txt TLE 5090 ms 15740 KB
test_06.txt AC 245 ms 4476 KB
test_07.txt TLE 5257 ms 31100 KB
test_08.txt AC 11 ms 1660 KB
test_09.txt AC 3018 ms 12668 KB
test_10.txt AC 192 ms 3452 KB
test_11.txt AC 235 ms 4476 KB
test_12.txt AC 658 ms 7548 KB
test_13.txt AC 254 ms 4476 KB
test_14.txt AC 464 ms 5500 KB
test_15.txt TLE 5257 ms 27004 KB
test_16.txt AC 524 ms 5500 KB
test_17.txt AC 3964 ms 13692 KB
test_18.txt AC 649 ms 5500 KB
test_19.txt AC 597 ms 6524 KB
test_20.txt AC 433 ms 5500 KB
test_21.txt AC 2 ms 892 KB
test_22.txt AC 415 ms 4476 KB
test_23.txt AC 6 ms 1276 KB
test_24.txt AC 282 ms 1148 KB
test_25.txt AC 286 ms 1148 KB
test_26.txt AC 65 ms 1020 KB
test_27.txt AC 88 ms 1020 KB
test_28.txt AC 283 ms 1148 KB
test_29.txt AC 286 ms 1148 KB
test_30.txt AC 15 ms 1020 KB
test_31.txt AC 3 ms 1020 KB
test_32.txt AC 283 ms 1148 KB
test_33.txt AC 287 ms 1148 KB
test_34.txt AC 7 ms 1020 KB
test_35.txt AC 53 ms 1020 KB
test_36.txt AC 286 ms 1148 KB