Submission #65132871

---

Source Code Expand

import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List

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

main :: IO ()
main = do
  [n,m] <- bsGetLnInts
  abcs <- replicateM m bsGetLnInts
  let ans = abc243e n m abcs
  print ans

bsGetLnInts :: IO [Int]
bsGetLnInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

abc243e :: Int -> Int -> [[Int]] -> Int
abc243e n m abcs = length [() | a:b:c:_ <- abcs, d ! (a,b) < pred (c * succ m)]
  where
    d = runSTUArray $ warshallFloyd (1,n) $ concat
        [[(a,b,c1),(b,a,c1)] | a:b:c:_ <- abcs, let c1 = pred $ c * succ m]

warshallFloyd :: (Int,Int)                       -- 頂点番号範囲
              -> [(Int,Int,Int)]                 -- グラフ
              -> ST s (STUArray s (Int,Int) Int) -- 距離
warshallFloyd bnds@(lb,ub) g =
  do
    d <- newArray ((lb,lb),(ub,ub)) maxBound
    forM_ g (\(a,b,c) -> writeArray d (a,b) c)
    forM_ (range bnds) (\k ->
      forM_ (range bnds) (\i -> do
        dik <- readArray d (i,k)
        when (dik < maxBound) $ do
          forM_ (range bnds) (\j -> do
            dkj <- readArray d (k,j)
            when (dkj < maxBound) $ do
              dij <- readArray d (i,j)
              let dikj = dik + dkj
              when (dikj < dij) (writeArray d (i,j) dikj)
            )
        )
      )
    return d

Submission Info

Judge Result