Submission #12068155

---

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

type Edge = (Int, Int, Int)
eFrm  (frm, _, _)  = frm
eTo   (_, to, _)   = to
eCost (_, _, cost) = cost

shortestPath :: Int -> V.Vector Edge -> Int -> IO (Maybe (V.Vector Int))
shortestPath s edges numV = do
  let numE = V.length edges
      inf = 10^9 :: Int

  d <- VM.new numV
  VM.set d inf
  VM.write d s 0

  let loop :: Int -> IO Bool
      loop i | i == numV = return True -- cyclic
             | otherwise = do update <- loop2 0 False
                              if update
                                then loop (i+1)
                                else return False

      loop2 :: Int -> Bool -> IO Bool
      loop2 j upd | j == V.length edges = return upd
                  | otherwise = do
                      let e = edges V.! j
                      d_frm <- VM.read d (eFrm e)
                      d_to  <- VM.read d (eTo e)
                      let ucond = d_frm /= inf && d_to > d_frm + eCost e
                          upd' = upd || ucond
                      when ucond $ VM.write d (eTo e) (d_frm + eCost e)
                      loop2 (j+1) upd'

  cyc <- loop 0
  res <- V.freeze d

  if cyc
    then return Nothing
    else return (Just res)

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

  edges <- V.replicateM m $ do
    [a, b, c] <- getIntList
    return (a-1, b-1, c)

  let edges_rev = V.map (\(a, b, c) -> (b, a, c)) edges

  costs <- fromJust <$> shortestPath 0 edges n
  costs_r <- fromJust <$> shortestPath 0 edges_rev n

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

  print $ solve 0 0

Submission Info

Judge Result