Submission #12067157

---

Source Code Expand

import           Control.Exception           (assert)
import           Control.Monad
import qualified Control.Monad.ST            as ST
import qualified Data.Array.IO               as IO
import qualified Data.Array.ST               as ST
import qualified Data.Array.Unboxed          as A
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import           Data.Foldable
import           Data.List
import           Data.Maybe
import qualified Data.Sequence               as Seq
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM
import           Debug.Trace

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine
getIntVec n = V.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

readInteger = fst . fromJust . BS.readInteger
readIntegerList = map readInteger . BS.words
getInteger = readInteger <$> BS.getLine
getIntegerList = readIntegerList <$> BS.getLine

warshallFloyd :: A.UArray (Int, Int) Int -> A.UArray (Int, Int) Int
warshallFloyd iarr = oarr
  where
    l  = (fst . fst . A.bounds) iarr
    l' = (snd . fst . A.bounds) iarr
    r  = (fst . snd . A.bounds) iarr
    r' = (snd . snd . A.bounds) iarr
    oarr = assert (l==l' && r==r') $ ST.runSTUArray $ do
      d <- ST.thaw iarr
      forM_ [l..r] $ \k ->
        forM_ [l..r] $ \i ->
          forM_ [l..r] $ \j -> do
            dik <- ST.readArray d (i,k)
            dkj <- ST.readArray d (k,j)
            dij <- ST.readArray d (i,j)
            when (dik + dkj < dij) $
              ST.writeArray d (i,j) (dik + dkj)
      return d

main = do
  [n, m, t] <- getIntList
  as <- getIntVec n

  let inf = 10^9 :: Int
  arr <- IO.newArray ((1,1),(n,n)) inf :: IO (IO.IOUArray (Int, Int) Int)
  forM_ [1..n] $ \i -> IO.writeArray arr (i,i) 0

  replicateM m $ do
    [a, b, c] <- getIntList
    IO.writeArray arr (a, b) c

  arr' <- IO.freeze arr :: IO (A.UArray (Int, Int) Int)

  let  costs = warshallFloyd arr'

       solve i r | i > n = r
                 | otherwise =
                   let waste = costs A.! (1, i) + costs A.! (i, 1)
                       rest = max 0 (t - waste)
                       gain = rest * as V.! (i-1)
                   in solve (i+1) (max r gain)

  print $ solve 1 0

Submission Info

Judge Result