Submission #38235250

---

Source Code Expand

import Control.Monad
import Control.Monad.ST
import Data.Array.ST
import Data.Array

main = do
  n <- readLn
  as <- map read . words <$> getLine
  ss <- replicateM n getLine
  let arr = abc286ep n as ss
  let aa = listArray (1,n) as
  q <- readLn
  replicateM_ q $ do
    [u,v] <- map read . words <$> getLine
    let ans = abc286em arr aa u v
    putStrLn ans

type DA = Array (Int,Int) (Int,Int) -- 距離の表

abc286ep :: Int       -- N
         -> [Int]     -- Ai
         -> [String]  -- Si
         -> DA        -- 距離の表
abc286ep n as ss = runSTArray action
  where
    action :: ST s (STArray s (Int, Int) (Int, Int))
    action = do
      arr <- newListArray ((1,1),(n,n)) $
        [ if sij == 'N' then (maxBound, 0) else (1, - ai)
        | (i,si,ai) <- zip3 [1..] ss as
        , (j,sij)   <- zip  [1..] si
        ]
      forM_ [1..n] (\k ->
        forM_ [1..n] (\i -> do
          dik <- readArray arr (i,k)
          when (dik < (maxBound, 0)) (
            forM_ [1..n] (\j -> do
              dkj <- readArray arr (k,j)
              when (dkj < (maxBound, 0)) $ do
                let dikj = add dik dkj
                dij <- readArray arr (i,j)
                when (dij > dikj) $ writeArray arr (i,j) dikj
              )
            )
          )
        )
      return arr

add (a,b) (c,d) = (a+c,b+d)

-- クエリ対応
abc286em :: DA            -- 距離の表
         -> Array Int Int -- Ai
         -> Int           -- Ui
         -> Int           -- Vi
         -> String        -- 答え
abc286em arr aa i j
  | k == maxBound = "Impossible"
  | otherwise     = unwords [show k, show $ aa ! j - a]
  where
    (k,a) = arr ! (i,j)

Submission Info

Compile Error

Loaded package environment from /home/contestant/.ghc/x86_64-linux-8.8.3/environments/default

Judge Result